Cod sursa(job #2529040)

Utilizator Raresr14Rosca Rares Raresr14 Data 22 ianuarie 2020 21:46:16
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,i,x,y,IS[100010],Niv[100010],niv,s[100010],f[100010],low[100010],comp;
stack<int> ST;
vector<int> L[100010],C[100010];
void dfs(int nod){
    niv++;
    Niv[nod]=niv;
    low[nod]=niv;
    s[nod]=1;
    f[nod]=1;
    ST.push(nod);
    for(int i=0;i<L[nod].size();i++){
        int vec=L[nod][i];
        if(f[vec]==0){
            dfs(vec);
            low[nod]=min(low[nod],low[vec]);
        }else
            if(s[vec])
                low[nod]=min(low[nod],low[vec]);
    }

    if(Niv[nod]==low[nod]){
        comp++;
        do{
            x=ST.top();
            C[comp].push_back(x);
            ST.pop();
            IS[x]=0;
        }while(x!=nod);
    }

}
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y;
        L[x].push_back(y);
    }
    for(i=1;i<=n;i++)
        if(f[i]==0)
            dfs(i);

    fout<<comp<<"\n";
    for(i=1;i<=comp;i++){
        for(int j=0;j<C[i].size();j++)
            fout<<C[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}