Cod sursa(job #1556748)

Utilizator mihai.constantinConstantin Mihai mihai.constantin Data 25 decembrie 2015 20:00:09
Problema Parcurgere DFS - componente conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int dmax = 100000;
const int dim = 1000000;

struct MUCHIE {int a, b;};
MUCHIE m[2*dim + 1];

int inc[dmax+1];
int k;

int viz[dmax+1];

int N,M, NR;

void DFS(int x)
{
    viz[x] = true;

    //printf("%d ", x);

    //PARCURG LISTA VECINILOR LUI X

    for(int i = inc[x]; m[i].a == x; i++)
        if(viz[ m[i].b ] == false) DFS(m[i].b);
}

bool exc(MUCHIE e1, MUCHIE e2)
{
    if(e1.a == e2.a) return e1.b < e2.b;
        else
            return e1.a < e2.a;
}

int main()
{
    freopen("dfs.in", "r", stdin);
    freopen("dfs.out", "w", stdout);

    int i, x, y;

    scanf("%d %d", &N, &M);
    for(i = 1; i <= M; i++)
    {
        scanf("%d %d", &x, &y);

        k++;
        m[k].a = x;
        m[k].b = y;

        k++;
        m[k].a = y;
        m[k].b = x;
    }

    sort(m+1, m+k+1, exc);

    /*for(i = 1; i <= k; i++) printf("%d ", m[i].a);
    printf("\n");
    for(i = 1; i <= k; i++) printf("%d ", m[i].b);
    printf("\n");*/

    inc[1] = 1;

    for(i = 2; i <= k; i++)
        if(m[i].a != m[i-1].a)
            inc[ m[i].a ] = i;

    //for(i = 1; i <= N; i++) printf("%d ", inc[i]);
    //printf("\n");

    for(i = 1; i <= N; i++)
        if(viz[i] == false)
        {
            NR++;
            DFS(i);
            //printf("\n");
        }

    printf("%d", NR);

    return 0;
}