Cod sursa(job #759672)

Utilizator razeraze raze raze Data 18 iunie 2012 22:52:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <cstring>
#include <vector>

#define maxN 100001

using namespace std;

ifstream in;
ofstream out;

vector <int> g[maxN];
int use[maxN];

inline void dfs(int nod)
{
    use[nod]=1;

    for(int i=0;i<g[nod].size();++i)
        if(!use[g[nod][i]]) dfs(g[nod][i]);
}

int main(int argc,char *argv[])
{
    int M,N,cnt,x,y;

    in.open("dfs.in");
    
    in>>N>>M;
    for(;M--;)
    {
        in>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    in.close();

    memset(use,0,sizeof(use));
    cnt=0;

    for(int i=1;i<=N;++i)
        if(!use[i]) dfs(i), ++cnt;

    out.open("dfs.out");

    out<<cnt<<'\n';

    out.close();

    return 0;
}