Cod sursa(job #177105)

Utilizator cretuMusina Rares cretu Data 12 aprilie 2008 12:24:59
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <vector>

using namespace std;

int m, n;
vector<vector<int> > a;
bool s[100001];

void DF(int nod)
{
    s[nod] = true;
    
    int i, x = a[nod].size();
    for (i = 0; i < x; i++)     
        if (!s[a[nod][i]]) DF(a[nod][i]);
}

int main()
{
    int v1, v2, i;
    ifstream fin("dfs.in");
    fin >> n >> m;
    
    a.resize(n+1);
    
    for (; m; m--)    
    {
        fin >> v1 >> v2;
        a[v1].push_back(v2);    
    }
    fin.close();
    
    int nr = 0;
    for (i = 1; i <= n; i++)
        if (!s[i]) 
        {
           ++nr;
           DF(i);           
        }
    
    ofstream fout("dfs.out");
    fout << nr << "\n";
    fout.close();
    
    return 0;    
}