Cod sursa(job #1822472)

Utilizator MithrilBratu Andrei Mithril Data 4 decembrie 2016 22:36:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");
int nrComp,n,m,x,y;
vector<char> color;
vector<int> parent;
vector<int> timpIntrare;
vector<int> timpIesire;
vector<int> adj[100001];
int timp;

void DFS(int nodStart)
{
    color[nodStart]='g';
    timpIntrare[nodStart]=timp++;
    for(auto i:adj[nodStart])if(color[i]=='w')
    {
        parent[i]=nodStart;
        DFS(i);
    }
    color[nodStart]='b';
    timpIesire[nodStart]=timp++;
}

int main()
{
    fin>>n>>m;
    timpIntrare.resize(n+1,-1);
    timpIesire.resize(n+1,-1);
    color.resize(n+1,'w');
    parent.resize(n+1,-1);
    for(int i=1;i<=m;i+=1)
    {
        fin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(int i=1;i<=n;i+=1)if(color[i]=='w')
    {
        nrComp+=1;
        DFS(i);
    }
    fout<<nrComp;
    fin.close();fout.close();
    return 0;
}