Cod sursa(job #1856550)

Utilizator testepbSorin Popa testepb Data 25 ianuarie 2017 01:07:52
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
struct nod
{
    int k,mu[1000];
};
nod n[100001];
int di[100001],nr,m,con,viz[100001];
void citire()
{   int x,y;
    f>>nr>>m;
    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        if(x!=y)
        {n[x].k++; n[y].k++;
        n[x].mu[n[x].k]=y; n[y].mu[n[y].k]=x;}
    }
}
void parcurgere(int x)
{   if(viz[x]==0) con++; viz[x]=1;
    for(int i=1;i<=n[x].k;i++)
        if(viz[n[x].mu[i]]==0)
    {
        viz[n[x].mu[i]]=1; parcurgere(n[x].mu[i]);
    }
}
void df()
{
    for(int j=1;j<=nr;j++)
        parcurgere(j);
    g<<con;
}
int main()
{
    citire(); df();
    return 0;
}