Cod sursa(job #1141962)

Utilizator OnimushaLordTiberiu Copaciu OnimushaLord Data 13 martie 2014 12:33:26
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
# include <cstdio>
# include <vector>
# define N 100010
# define pb push_back
# define ED end
# define BG begin

using namespace std;

int sel[N];
vector <int> G[N];
int n,m,x,y;

void load()
{
    int i;
    scanf("%d %d\n", &n, &m);
    for(i=1; i<=m; ++i)
    {
        scanf("%d %d\n", &x, &y);
        G[x].pb(y);
        G[y].pb(x);
    }
}
void df(int x)
{
    int i;
    sel[x]=true;
    for(i=0; i<G[x].size(); ++i)
        if(!sel[G[x][i]]) df(G[x][i]);
}
void solve()
{
    int nr=0,i;
    load();
    for(i=1; i<=n; ++i)
        if(!sel[i])
        {
            df(i);
            nr++;
        }
    printf("%d\n", nr);
}
int main()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);
    solve();
    return 0;
}