Cod sursa(job #1339719)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 11 februarie 2015 08:19:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>
#include <vector>
int counter;
int vis[100001];
std::vector<int> *adj;
int n,m;
void dfs(int pos)
{
     vis[pos]=counter;
     std::vector<int>::iterator it;
     for(it=adj[pos].begin();it!=adj[pos].end();++it)
     {
            if(vis[*it]==0) dfs(*it);
     }
}
int main()
{
    freopen ("dfs.in","r",stdin);
    freopen ("dfs.out","w",stdout);
    scanf("%d%d",&n,&m);
    adj=new std::vector<int>[n+1];
    int p1,p2;
    for(int i=1;i<=m;i++)
    {
            scanf("%d%d",&p1,&p2);
            adj[p1].push_back(p2);
            adj[p2].push_back(p1);
    }
    for(int i=1;i<=n;i++)
    {
            if(vis[i]==0) 
            {
                          counter++;
                          dfs(i);
            }
    }
    printf("%d\n",counter);
}