Cod sursa(job #1728226)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 12 iulie 2016 15:27:38
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,a[1001][1001],x,y,i,j,minim,maxim,c[1001],m,k,nrc;
int main()
{
    f>>n>>m;
    while(m>0)
    {
        f>>x>>y;
        a[x][y]=a[y][x]=1;
        m--;
    }
    for(i=1;i<=n;i++)
    {
        c[i]=i;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(a[i][j]==1)
            {
                if(c[i]!=c[j])
                {
                    if(c[i]<c[j])
                    {
                        minim=c[i];
                        maxim=c[j];
                    }
                    else
                    {
                        minim=c[j];
                        maxim=c[i];
                    }
                }
            }
            for(k=1;k<=n;k++)
            {
                if(c[k]==maxim)
                {
                    c[k]=minim;
                }
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        if(c[i]!=0)
        {
            nrc++;
            for(j=i+1;j<=n;j++)
            {
                if(c[j]==c[i])
                {
                    c[j]=0;
                }
            }
        }
    }
    g<<nrc;
    return 0;
}