Cod sursa(job #854559)

Utilizator RamaStanciu Mara Rama Data 13 ianuarie 2013 18:55:48
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include<stdio.h>
#include<vector>

using namespace std;
int mark[100001];
vector <int> G[100001];
void dfs(int a)
{
     mark[a]=1;
     for(int i=0; i < G[a].size();i++)
             if(mark[G[a][i]]==0)
             dfs(G[a][i]);
}
int main()
{
    FILE*f,*g;
    f=fopen("dfs.in","r");
    g=fopen("dfs.out","w");
    int N,M,k=0;
    fscanf(f,"%d%d",&N,&M);
    int x,y;
    for(int i=1;i<=M;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for(int i=1;i<=N;i++)
    {
        if(mark[i]==0)
            {
                dfs(i);
                k++;
            }
    }
    fprintf(g,"%d",k);
    return 0;
}