Cod sursa(job #952524)

Utilizator acomAndrei Comaneci acom Data 23 mai 2013 17:04:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<cstdio>
#include<vector>
using namespace std;
vector <int> G[100005];
int m,n,nr,viz[100005],rez,x,y;
void dfs(int s, int val)
{
    int i,z;
    viz[s]=val;
    for (i=0;i<G[s].size();++i)
        {
            z=G[s][i];
            if (!viz[z]) dfs(z,val);
        }
}
int main()
{
    int i;
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;++i)
        {
            scanf("%d%d",&x,&y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
    for (i=1;i<=n;++i)
        if (!viz[i])
            {
                ++nr;
                dfs(i,nr);
            }
    printf("%d\n",nr);
    return 0;
}