Cod sursa(job #2085549)

Utilizator pistvanPeter Istvan pistvan Data 10 decembrie 2017 13:18:09
Problema Parcurgere DFS - componente conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>
#include <stack>
#define MaxN 100001
using namespace std;

int N, M, x, y, comp=0, z;
vector<int> AdList[MaxN];
bool viz[MaxN];

void Read()
{
    ifstream f("dfs.in");
    f>>N>>M;
    for (int i=1;i<=N;i++)
        AdList[i].push_back(0);
    for (int i=0;i<M;i++)
    {
        f>>x>>y;
        AdList[x].push_back(y);
        AdList[x][0]++;
        AdList[y].push_back(x);
        AdList[y][0]++;
    }
}

void DFS(int a)
{
    stack<int> S;
    int i;
    S.push(a);
    while (!S.empty())
    {
        z=S.top();
        i=1;
        while (i<=AdList[z][0] && viz[AdList[z][i]])
            i++;
        if (i!=AdList[z][0]+1)
        {
            S.push(AdList[z][i]);
            viz[AdList[z][i]]=1;
        }
        S.pop();
    }
    comp++;
}

int main()
{
    Read();
    for (int i=1;i<=N;i++)
        if (!viz[i])
            DFS(i);
    ofstream g("dfs.out");
    g<<comp;
}