Cod sursa(job #1489988)

Utilizator tiby10Tibi P tiby10 Data 22 septembrie 2015 16:04:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<vector>
#include<fstream>
#include<iostream>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define MAXN 100005

int n, m, S[MAXN], e, CTC[MAXN], ctc;
vector<int> G[MAXN], Gt[MAXN], Nodes[MAXN];
bool used[MAXN];

void dfsstep1(int node) {
 used[node] = 1;
 for(auto vec : G[node]) {
  if(!used[vec])
   dfsstep1(vec);
 }
 S[++e] = node;
}

void dfsstep2(int node) {
 CTC[node] = ctc;
 for(auto vec : Gt[node])
  if(!CTC[vec])
   dfsstep2(vec);
}

int main() {
    int a, b, i;
    fin>>n>>m;
    while(m--) {
        fin>>a>>b;
        G[a].push_back(b);
        Gt[b].push_back(a);
    }
     for(i=1; i<=n; ++i)
        if(!used[i])
            dfsstep1(i);

    for(i=n; i>=1; i--)
        if(!CTC[S[i]])
            ++ctc, dfsstep2(S[i]);

     for(i=1; i<=n; i++)
        Nodes[CTC[i]].push_back(i);
    fout<<ctc<<'\n';
    for(i=1; i<=ctc; ++i){
        for(auto comp : Nodes[i])
            fout<<comp<<" ";
        fout<<'\n';
    }
    return 0;
}