Cod sursa(job #2125160)

Utilizator infomaxInfomax infomax Data 8 februarie 2018 01:44:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>

using namespace std;

FILE *F=fopen("dfs.in", "r"), *G=fopen("dfs.out", "w");

int n, m, x, y, grd[100005], L[100005], g[200005], K;
bitset<100005> v;
vector<pair<int, int> > a;

void dfs(int nod){
    v[nod]=1;
    int x = grd[nod-1];
    int y = grd[nod];
    for(int i = x; i < y; ++ i){
        if(!v[g[i]]){
            dfs(g[i]);
        }
    }
}

int main()
{
    char ch = fgetc(F);
    while(!isdigit(ch)) ch=fgetc(F);
    while(isdigit(ch)){
        n = n*10+ch-'0';
        ch=fgetc(F);
    }
    while(!isdigit(ch)) ch=fgetc(F);
    while(isdigit(ch)){
        m = m*10+ch-'0';
        ch=fgetc(F);
    }
    for(int i = 1; i <= m; ++ i){
        x=0; y=0;
        while(!isdigit(ch)) ch=fgetc(F);
        while(isdigit(ch)){
            x = x*10+ch-'0';
            ch=fgetc(F);
        }
        while(!isdigit(ch)) ch=fgetc(F);
        while(isdigit(ch)){
            y = y*10+ch-'0';
            ch=fgetc(F);
        }
        grd[x]++; grd[y]++;
        a.push_back({x, y});
    }
    for(int i = 1; i <= n; ++ i){
        grd[i]+=grd[i-1];
        L[i]=grd[i-1];
    }
    for(int i = 1; i <= m; ++ i){
        x=a[i-1].first;
        y=a[i-1].second;
        g[L[x]++]=y;
        g[L[y]++]=x;
    }
    for(int i = 1; i <= n; ++ i){
        x = grd[i-1];
        y=grd[i];
        sort(g+x, g+y);
    }
    for(int i = 1; i <= n; ++ i){
        if(!v[i]){
            dfs(i);
            K++;
        }
    }
    fprintf(G, "%d",K);
    return 0;
}