连通图

题目描述

每组数据的第一行是两个整数 n 和 m（0<=n<=1000）。n 表示图的顶点数目，m 表示图中边的数目。随后有 m 行数据，
每行有两个值 x 和 y（0<x, y <=n），表示顶点 x 和 y 相连，顶点的编号从 1 开始计算。输入不保证这些边是否重复。

    对于每组输入数据，如果所有顶点都是连通的，输出"YES"，否则输出"NO"。

4 3
1 2
2 3
3 2
3 2
1 2
2 3
0 0

NO
YES

#include<cstdio>
#include<vector>
using namespace std;

vector<int> Graph[1010];
bool visit[1010];

void DFS(int v){
    visit[v] = true;
    for(int i = 0; i < Graph[v].size(); ++i){
        int p = Graph[v][i];
        if(!visit[p])
            DFS(p);
    }
}

void Init(int n){
    for(int i = 1; i <= n ; ++i){
        visit[i] = false;
    }
}

int main(void){
    int n,m,x,y;
    int i,j;
    while(scanf("%d %d",&n,&m) != EOF){
        if(n == 0 && m == 0) break;
        Init(n);
        for(i = 1; i <= m; ++i){
            scanf("%d %d",&x,&y);
            for(j = 0; j < Graph[x].size(); ++j){
                if(Graph[x][j] == y)
                    break;
            }
            if(j >= Graph[x].size()){
                Graph[x].push_back(y);
                Graph[y].push_back(x);
            }
        }
        DFS(1);
        for(i = 1; i <= n; ++i){
            if(!visit[i])
                break;
        }
        if(i >= n+1)
            printf("YES\n");
        else
            printf("NO\n");

    }
    return 0;
}