Cod sursa(job #1159810)

Utilizator Mihai_ChihaiMihai Chihai Mihai_Chihai Data 29 martie 2014 21:23:28
Problema Parcurgere DFS - componente conexe Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.57 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

int a[10000][10000],viz[10000],n,m,i,j;
int dfs(int k)
{
    viz[k]=1;
    for (int i=1;i<=n;i++)
    if (!viz[i] && a[k][i]) dfs(i);
}
int main()
{

    fin>>n>>m;
    int x,y;
    for (int i=1;i<=m;i++) {
            fin>>x>>y;
            a[x][y]=a[y][x]=1;
            }
    for (i=1;i<=n;i++) viz[i]=0;
    int ans=0;
    for (i=1;i<=n;i++)
    if (!viz[i]) {dfs(i); ans++;}
    fout<<ans;
    fin.close();
    fout.close();
}