Cod sursa(job #3198431)

Utilizator andreigspdAndrei Gospodaru andreigspd Data 29 ianuarie 2024 11:54:16
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,x,y,inS[100001],dfn[100001],low[100001],nrc,cnt;
vector<int>g[100001],c;
vector<vector<int> >rez;
stack<int>s;
void tarjan(int k){
 dfn[k]=low[k]=++cnt;
 s.push(k);
 inS[k]=1;
 for(int i:g[k]){
    if(!dfn[i]){
        tarjan(i);
        low[k]=min(low[k],low[i]);
    }
    else{
        if(inS[i]){
            low[k]=min(low[k],dfn[i]);
        }
    }
 }
 if(low[k]==dfn[k]){
    nrc++;
    c.clear();
    while(true){
        int val=s.top();
        s.pop();
        inS[val]=0;
        c.push_back(val);
        if(val==k)break;
    }
    rez.push_back(c);
 }
}
int main(){
 fin>>n>>m;
 for(int i=1;i<=m;i++){
    fin>>x>>y;
    g[x].push_back(y);
 }
 for(int i=1;i<=n;i++){
    if(!dfn[i]){
        cnt=0;
        tarjan(i);
    }
 }
 fout<<nrc<<'\n';
 for(int i=0;i<rez.size();i++){
    sort(rez[i].begin(),rez[i].end());
 }
 for(int i=0;i<rez.size();i++){
    for(int j=0;j<rez[i].size();j++){
        fout<<rez[i][j]<<' ';
    }
    fout<<'\n';
 }

}