Cod sursa(job #157418)

Utilizator DorinOltean Dorin Dorin Data 12 martie 2008 23:59:32
Problema Parcurgere DFS - componente conexe Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
# include <stdio.h>
# include <vector>

using namespace std;

# define input "dfs.in"
# define output "dfs.out"

# define maxN 100000

vector < vector <int> > v;
bool u[maxN];
int i,n,x,y,res,m;

void dfs(int nod)
{
     u[nod] = 1;
     for(int j = 0;j < v[nod].size();j++)
        if(!u[v[nod][j]])
            dfs(v[nod][j]);
}

int main()
{
    freopen(input, "r", stdin);
    freopen(output, "w", stdout);
    
    scanf("%d%d",&n,&m);
    
    v.resize(n+1);
    
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    
    for(i=1;i<=n;i++)
       if(!u[i])
       {
                res++;
                dfs(i);
       }
        
    
    printf("%d",res);
    
    return 0;
}