Cod sursa(job #1548022)

Utilizator DobosDobos Paul Dobos Data 10 decembrie 2015 11:42:17
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int NMAX = 100005;
const int BMAX = 500;
char buffer[BMAX + 1];
int poz = BMAX ;
vector < int > G[NMAX],Gi[NMAX],Gf[NMAX],where;
bitset < BMAX > viz;
stack < int > bumt;
void parsare(int &x){
    while(!isdigit(buffer[poz])){
        poz ++;
        if(poz > BMAX){
            poz = 0;
            fin.read(buffer,BMAX);
        }
    }
    x = 0;
    while(isdigit(buffer[poz])){
        x = x*10 + (buffer[poz] - '0');
        poz++;
        if(poz > BMAX){
            poz = 0;
            fin.read(buffer,BMAX);
        }
    }
}
void dfs(int nod){
    viz[nod] = 1;
    for(int i = 0;i < Gi[nod].size(); i++){
        if(viz[Gi[nod][i]] == 0)
            dfs(Gi[nod][i]);
    }
    bumt.push(nod);
}
void dms(int nod,int cont){
    where[nod] = cont;
    for(int i = 0; i < Gf[nod].size();i++){
        if(where[Gf[nod][i]] == 0){
            dms(Gf[nod][i],cont);
        }
    }
}
int main()
{
    int n,m,x,y,cont;
    parsare(n); parsare(m);
    for(int i = 1; i <= m; i++){
        parsare(x); parsare(y);
        Gi[x].push_back(y);
        Gf[y].push_back(x);
    }
    for(int i = 1;i <= n; i++){
        if(viz[i] == 0){
            dfs(i);
        }
    }
    where.resize( n + 1);
    cont  = 1;
    while(!bumt.empty()){
        if(where[bumt.top()] == 0){
            dms(bumt.top(),cont);
            cont ++;
        }
        bumt.pop();
    }
    for(int i = 1; i <= n; i++){
        G[where[i]].push_back(i);
    }
    fout << cont - 1 << "\n";
    for(int j = 1; j < cont; j++){
        for(int i = 0; i < G[j].size();i++){
            fout << G[j][i] << " ";
        }
        fout << "\n";
    }
    return 0;
}