Cod sursa(job #3147392)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 26 august 2023 08:32:04
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include<bits/stdc++.h>
using namespace std;
ifstream F("ctc.in");
ofstream G("ctc.out");
int n,m,i,j,k,r,u[100001],v[100001];
vector<int> g[100001];
stack<int> s,z[100001];
bitset<100001> w;
void A(int i)
{
    int j;
    u[i]=v[i]=++k,s.push(i),w[i]=1;
    for(int j:g[i])
        if(!u[j])
            A(j),v[i]=min(v[i],v[j]);
        else if(w[j])
            v[i]=min(v[i],u[j]);
    if(u[i]==v[i]) {
        for(j=0;j!=i;j=s.top(),s.pop(),w[j]=0,z[r].push(j));
        ++r;
    }
}
int main()
{
    for(F>>n>>m;m--;F>>i>>j,g[i].push_back(j));
    for(i=1;i<=n;++i)
        if(!u[i])
            A(i);
    for(G<<r,i=0;i<r;++i)
        for(G<<'\n';!z[i].empty();G<<z[i].top()<<' ',z[i].pop());
    return 0;
}