Cod sursa(job #2710863)

Utilizator radugnnGone Radu Mihnea radugnn Data 23 februarie 2021 11:03:07
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define DIM 100010
using namespace std;
ifstream fin ("ctc.in");
ofstream fout("ctc.out");
int n, m, a, b, cnt, ctc;
int v[DIM],low[DIM],niv[DIM];
vector<int> Sol[DIM],L[DIM];
stack<int> S;
void dfs(int nod){
    cnt++;
    v[nod]=1;
    low[nod]=niv[nod]=cnt;
    S.push(nod);
    for(int i=0; i<L[nod].size(); i++){
        int vecin=L[nod][i];
        if(!niv[vecin]){
            dfs(vecin);
            low[nod]=min(low[nod],low[vecin]);
        }
        else if(v[vecin]){
            low[nod]=min(low[nod],low[vecin]);
        }
    }
    if(niv[nod]==low[nod]){
        ctc++;
        int x;
        do{
           x=S.top();
           Sol[ctc].push_back(x);
           S.pop();
           v[x]=0;
        }while(x!=nod);
    }

}
int main(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>a>>b;
        L[a].push_back(b);
    }
    for(int i=1;i<=n;i++){
        if(!niv[i])
            dfs(i);
    }
    fout<<ctc<<"\n";
    for(int i=1;i<=ctc;i++, fout<<"\n")
        for(int j=0;j<Sol[i].size();j++)
            fout<<Sol[i][j]<<" ";

    return 0;
}