Cod sursa(job #2170175)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 14 martie 2018 22:39:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
list <int> G[Nmax];
bool viz[Nmax];
int N;
stack <int> st;
void DFS(int x)
{
    st.push(x);
    while(!st.empty())
    {
        x=st.top();
        viz[x]=true;
        while(!G[x].empty() and viz[G[x].front()]) G[x].pop_front();
        if(!G[x].empty())
        {
            st.push(G[x].front());
            G[x].pop_front();
        }
        else st.pop();
    }
}
int main()
{
    int n,i,j,m,k;
    f>>n>>m;
    for(k=0;k<m;k++)
    {
        f>>i>>j;
        G[i].push_back(j);
        G[j].push_back(i);
    }
    for(i=1;i<=n;i++)
        if(!viz[i])
        {
            ++N;
            DFS(i);
        }
    g<<N;

    return 0;
}