hihoCoder 1322 : 树结构判定（dfs 或并查集）

╰+哭是因爲堅強的太久メ 2024-02-17 22:10 27阅读 0赞

#### \#1322 : 树结构判定 ####

时间限制: 10000ms

单点时限: 1000ms

内存限制: 256MB

#### 描述 ####

给定一个包含 N 个顶点 M 条边的无向图 G ，判断 G 是不是一棵树。

#### 输入 ####

第一个是一个整数 T ，代表测试数据的组数。 (1 ≤ T ≤ 10)

每组测试数据第一行包含两个整数 N 和 M 。(2 ≤ N ≤ 500, 1 ≤  M ≤ 100000)

以下 M 行每行包含两个整数 a 和 b ，表示顶点 a 和顶点  b 之间有一条边。(1 ≤ a, b ≤ N)

#### 输出 ####

对于每组数据，输出YES或者NO表示 G 是否是一棵树。

样例输入

2
    3 2
    3 1
    3 2
    5 5
    3 1
    3 2
    4 5
    1 2
    4 1

样例输出

YES
    NO

分析：dfs 或并查集，判断一棵树，n个结点，则边应为n-1，所有点都被连在内

AC代码：

#include<cstdio>
    #include<cstring>
    #include<vector>
    using namespace std;
    const int maxn=500+10;
    vector<int>g[maxn];
    int vis[maxn];
    int n,m;
    int cnt;
    
    void dfs(int i){
      	for(int j=0;j<g[i].size();j++){
      		int t=g[i][j];
      		if(!vis[t]){
      			vis[t]=1;
      			cnt--;
      			dfs(t);
    		  }
    	  }
    }
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d%d",&n,&m);
    		for(int i=0;i<m;i++){
    			int a,b;
    			scanf("%d%d",&a,&b);
    			g[a].push_back(b);
    			g[b].push_back(a);
    		}
    		
    		if(m==n-1){
    		memset(vis,0,sizeof(vis));
    		cnt=m;
    		vis[1]=1;
    		dfs(1);
    		if(cnt==0)
    		  printf("YES\n");
    		else 
    		  printf("NO\n");			
    		}
    		else printf("NO\n");
    		
    		for(int i=0;i<maxn;i++)g[i].clear();  //清0！！ 
    	}
    	return 0;
    }