Cod sursa(job #1375548)

Utilizator kira2071Diana C kira2071 Data 5 martie 2015 13:35:52
Problema Parcurgere DFS - componente conexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <cstdio>
using namespace std;

int viz[100100],n,m,nrc;

void config(int x, int y)
{
for(int i=1;i<=n;i++)
    if(viz[i]==y)
        viz[i]=x;
}

int main()
{
int x,i,y,nr=0;
FILE *f=fopen("dfs.in","r");
fscanf(f,"%d %d",&n,&m);
for(i=1;i<=m;i++)
    {
    fscanf(f,"%d %d",&x,&y);
    if(viz[x]==0 && viz[y]==0)
        {
        nr++;nrc++;
        viz[x]=viz[y]=nr;
        }
    else
        if(viz[x]!=0 && viz[y]==0)
            viz[y]=viz[x];
        else
            if(viz[x]==0 && viz[y]!=0)
                viz[x]=viz[y];
            else
                {config(viz[x],viz[y]);
                nrc--;}
    }
for(i=1;i<=n;i++)
    if(viz[i]==0)
        nrc++;
ofstream g("dfs.out");
g<<nrc;


return 0;
}