Cod sursa(job #916303)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 16 martie 2013 12:16:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>
using namespace std;

const int MAX_N = 100002;

int N, M, x, y, Res;
int st[MAX_N], m[MAX_N];
vector < int > v[MAX_N];

int main()
{
    ifstream f("dfs.in");
    ofstream g("dfs.out");

    f >> N >> M;
    for(int i = 1; i <= M; ++i)
        f >> x >> y, v[x].push_back(y), v[y].push_back(x);
    
    for(int k = 1; k <= N; ++k)
        if(!m[k])
        {
            ++Res;
            int top = 1;
            st[top] = k;
            while(top)
            {
                 int now = st[top], ok = 1;
                 m[now] = 1;
                 for(int i = 0; i < v[now].size(); ++i)
                     if(!m[ v[now][i] ])
                         ++top, st[top] = v[now][i], i = v[now].size(), ok = 0;
                 top -= ok;
            }
        }

     g << Res << '\n';

     f.close();
     g.close();

     return 0;
}