Cod sursa(job #864680)

Utilizator nosurrender99Bura Bogdan nosurrender99 Data 25 ianuarie 2013 16:51:26
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

fstream f("dfs.in" , ios::in), g("dfs.out", ios::out);
int n,m,tr=0;
bool v[100000];
vector <int> G[100000];
stack<int> s;

int main()
{
    f>>n>>m;
    for(;m;--m)
    {
        int a,b;
        f>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
    {
        if (v[i]==false)
        {
            tr++;
            int fr=i;
            s.push(i);
            while (!s.empty())
            {
                int front=s.top();
                for(int i=0;i<G[front].size();i++)
                {
                    if (v[G[front][i]]==false)
                    {
                        s.push(G[front][i]);
                        v[G[front][i]]=true;
                    }
                }
                s.pop();
            }
        }
    }
    g<<tr<<'\n';

    return 0;
}