Cod sursa(job #1473136)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 18 august 2015 17:14:58
Problema Parcurgere DFS - componente conexe Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define fin "dfs.in"
#define fou "dfs.out"
using namespace std;
ifstream t1(fin);
ofstream t2(fou);
vector<int> rel[100000];
stack<int> stiva;
int n,m,nrcomp;
short viz[100010];

void df(int x)
{
    int i;
    viz[x]=1;
    for(i=0;i<rel[x].size();i++)
        if(viz[rel[x][i]]==0) df(rel[x][i]);
}

int main()
{
    t1>>n>>m;
    int i,n1,n2,j;
    for(i=1;i<=m;i++)
    {
        t1>>n1>>n2;
        rel[n1].push_back(n2);
        rel[n2].push_back(n1);
    }
    for(i=1;i<=n;i++)
        if(viz[i]!=1)
        {
            nrcomp++;
            df(i);
        }
    t2<<nrcomp<<'\n';
    t1.close();
    t2.close();
    return 0;
}