Cod sursa(job #873216)

Utilizator valexVochescu Alexandru valex Data 6 februarie 2013 22:52:33
Problema Parcurgere DFS - componente conexe Scor 55
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    int j,aux,n,m,i,nr=0,nre=0,a,b;
    scanf("%d %d",&n,&m);
    vector<int> v(n);
    for (i=1;i<=n;i++)
        v[i]=i;
    nr=n;
    for (i=1;i<=m;i++)
    {
        scanf("%d %d",&a,&b);
        if (v[a]!=v[b])
        {
            if (a>b)
            {
                aux=a;
                a=b;
                b=aux;
            }
            nr--;
            aux=v[b];
            for (j=1;j<=n;j++)
                if (v[j]==aux)
                {
                    v[j]=v[a];
                }
            v[b]=v[a];
        }
    }
    printf("%d",nr);
}