Cod sursa(job #2542983)

Utilizator CandyBucherGaube Robert Gabriel CandyBucher Data 10 februarie 2020 19:15:44
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
int n,id=0,ids[100010],low[100010],ctc=0;
ofstream o("ctc.out");
ifstream f("ctc.in");
vector <int> v[100010],cc[100010];
stack <int> S;
bool onStack[100010],viz[100010];
void dfs(int k){
    ids[k]=low[k]=++id; int i;
    S.push(k); onStack[k]=1;
    viz[k]=1;
    for(int i : v[k]){
        if(!viz[k]){
            dfs(i);
            low[k]=min(low[k],low[i]);
        }
        else if(onStack[i]) low[k]=min(low[k],low[i]);
    }
    if(ids[k]==low[k]){
        ctc++;
        while(1){
            cc[ctc].push_back(S.top());
            onStack[S.top()]=0;
            if(S.top()==k){
                S.pop();
                break;
            }
            S.pop();
        }
    }
}
int main(){
    int m,j;
    f>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        f>>x>>y;
        v[x].push_back(y);
    }

    for(int i=1;i<=n;i++)
        if(!viz[i]) dfs(i);

    o<<ctc<<"\n";
    for(int i=1;i<=ctc;i++){
        for(int j : cc[i])
            o<<j<<" ";
        o<<"\n";
    }
}