Cod sursa(job #1376728)

Utilizator OnimushaLordTiberiu Copaciu OnimushaLord Data 5 martie 2015 18:33:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
# include <cstdio>
# include <vector>
# define N 100010
# define pb push_back
# define vecin (*it)

using namespace std;

vector <int> G[N];
vector <int> :: iterator it;

int sel[N];
int i,m,n,x,y;
int  nr;

void df(int nod)
{
    sel[nod]=true;
    for(vector <int> :: iterator it=G[nod].begin(); it!=G[nod].end(); ++it)
        if(!sel[vecin])
            df(vecin);

}
int main()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    scanf("%d %d\n", &n, &m);
    for(i=1; i<=m; ++i)
    {
        scanf("%d %d", &x, &y);
        G[x].pb(y);
        G[y].pb(x);
    }

    for(i=1; i<=n; ++i)
        if(!sel[i])
        {
            nr++;
            df(i);
        }

    printf("%d\n", nr);

    fclose(stdin);
    fclose(stdout);
    return 0;
}