Cod sursa(job #159861)

Utilizator sealTudose Vlad seal Data 14 martie 2008 14:39:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
using namespace std;
#include<cstdio>
#include<vector>
#define Nm 100001
char Viz[Nm];
int n,ans;
vector<int> G[Nm];

void read()
{
    char S[14];
    int m,x,y,i;

    freopen("dfs.in","r",stdin);
    scanf("%d%d ",&n,&m);
    while(m--)
    {
        gets(S);
        for(x=i=0;S[i]!=' ';++i)
            x=x*10+S[i]-'0';
        for(y=0,++i;S[i];++i)
            y=y*10+S[i]-'0';
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void DFS(int x)
{
    vector<int>::iterator it;

    Viz[x]=1;
    for(it=G[x].begin();it!=G[x].end();++it)
        if(!Viz[*it])
            DFS(*it);
}

void solve()
{
    int i;

    for(i=1;i<=n;++i)
        if(!Viz[i])
        {
            DFS(i);
            ++ans;
        }
}

void write()
{
    freopen("dfs.out","w",stdout);
    printf("%d\n",ans);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}