Cod sursa(job #1235209)

Utilizator afkidStancioiu Nicu Razvan afkid Data 28 septembrie 2014 23:19:34
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#include <vector>

using namespace std;
const char InFile[]="dfs.in";
const char OutFile[]="dfs.out";
const int DIMN=100010;

int n,m,cnt,visited[DIMN];
vector<int> G[DIMN];


void addEdge(int v,int w)
{
    G[v].push_back(w);
    G[w].push_back(v);
}

void DFSutil(int v)
{
    visited[v]=1;
    vector<int>::iterator it;
    for(it=G[v].begin();it!=G[v].end();++it)
        if(visited[*it]==0)
            DFSutil(*it);
}
void DFS()
{
    for(int i=1;i<=n;++i)
        if(visited[i]==0)
        {
          ++cnt;
          DFSutil(i);
        }
}


int main()
{
    int a,b;
    freopen(InFile,"r",stdin);
    freopen(OutFile,"w",stdout);

    scanf("%d %d",&n,&m);
    cnt=0;
    for(int i=1;i<=n;++i)
        visited[i]=0;
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d",&a,&b);
        addEdge(a,b);
    }
    DFS();
    printf("%d\n",cnt);
    return 0;
}