Cod sursa(job #1089591)

Utilizator oancea_horatiuOancea Horatiu oancea_horatiu Data 21 ianuarie 2014 19:47:29
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <stack>
#include <string>

using namespace std;
ifstream d("dfs.in");
ofstream o("dfs.out");


void readGraph(int& n, int& m, vector<int> v[100001])
{
    int x,y;

    d>>n>>m;
    for (int i=1;i<=n;i++)
    {
        d>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

int getComp(vector<int> v[100001], int n, int m)
{
    stack<int> s;
    int a[100001];
    int i,k=0,x;
    vector<int>::iterator it;

    for (i=1;i<=n;i++)
    {
        if (a[i]==0)
        {
            k++;
            s.push(i);

            while (!s.empty())
            {
                x=s.top();
                s.pop();
                for (it=v[x].begin();it!=v[x].end();++it)
                {
                    if (a[*it]==0)
                    {
                        a[*it]=k;
                        s.push(*it);
                    }
                }
            }
        }
    }
    return k;
}

void returnAnswer(int x)
{
    o<<x;
}

int main()
{
    vector<int> v[100001];
    vector<int>::iterator it;
    int n,m;


    readGraph(n,m,v);
    returnAnswer(getComp(v,n,m));

}