记录编号	322235	评测结果	AAAAA
题目名称	[轻工业学院ACM 2016] 蛤玮的机房	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2016-10-14 20:44:35	内存使用	0.78 MiB

/*
	Name: 蛤玮的机房 
	Copyright: 
	From： http://cogs.pro/cogs/problem/problem.php?pid=2253
	Author: Go灬Fire 
	Date: 14/10/16 20:42
	Description: 此代码用Tarjian缩点，还有并查集的做法上另一个号
					做的时候想麻烦了，还统计了入度为0的连通块的个数
					其实只要输出总连通块的个数-1即可，毕竟让求把连通块连通的最小路径数 
*/
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<stack>
#include<iostream>
#define Begin freopen("HWnetbar.in","r",stdin);freopen("HWnetbar.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
using namespace std;
const int maxn=200;
struct Edge{
	int from,next,to;
}e[maxn*maxn];
int n,m,len,head[maxn],Dfn[maxn],Low[maxn],Time,num;
bool flag[maxn];
stack<int> q; 
void Init();
void Insert(int x,int y){
	len++;e[len].from=x;e[len].to=y;e[len].next=head[x];head[x]=len;
}
void Dfs(int x){
	Low[x]=Dfn[x]=++Time;flag[x]=1;q.push(x);
	for(int i=head[x];i;i=e[i].next){
		int j=e[i].to;
		if(!Dfn[j]){
			Dfs(j);
			Low[x]=min(Low[x],Low[j]);
		}
		else if(flag[j])Low[x]=min(Low[x],Dfn[j]);
	}
	if(Low[x]==Dfn[x]){
		num++;int k;
		do{
			k=q.top();q.pop();
			flag[k]=0;
		}while(k!=x);
	}
}
int main(){
    Begin;
   	int T;scanf("%d",&T);
   	while(T--)Init();
    //system("pause");
    End;
    return 0;
}
void Init(){
	while(!q.empty())q.pop();Time=0;num=0;len=0;
	memset(e,0,sizeof(e));memset(head,0,sizeof(head));
	memset(Dfn,0,sizeof(Dfn));memset(Low,0,sizeof(Low));
	memset(flag,0,sizeof(flag));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		Insert(x,y);Insert(y,x);
	}
	for(int i=1;i<=n;i++)if(!Dfn[i])Dfs(i);
	printf("%d\n",num-1);
}