Cod sursa(job #1133757)

Utilizator omerOmer Cerrahoglu omer Data 5 martie 2014 16:16:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include<stdio.h>
#include<vector>
#include<stack>
using namespace std;
FILE *f,*g;
vector<int> veci[100001];
vector<int>::iterator it;
stack<int> dfs;
int comp[100001],l,n,m,x,y,i,j;

int main()
{
    f=fopen("dfs.in","r");
    g=fopen("dfs.out","w");
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
        {
           fscanf(f,"%d%d",&x,&y);
           veci[x].push_back(y);
           veci[y].push_back(x);
        }

    for(i=1;i<=n;i++)
        {
            if (!comp[i])
                {
                    l++;
                    dfs.push(i);
                    while(!dfs.empty())
                        {
                            j=dfs.top();
                            dfs.pop();
                            comp[j]=l;
                            it=veci[j].begin();
                            while(it!=veci[j].end())
                                {
                                    if (!comp[*it]) dfs.push(*it);
                                    it++;
                                }
                        }
                }
        }
    fprintf(g,"%d",l);

    return 0;
}