Cod sursa(job #3147394)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 26 august 2023 08:40:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 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],q[200000],z;
vector<int> g[100001];
stack<int> s;
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,q[z++]=j);
        ++r,q[z++]=0;
    }
}
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<<'\n',i=0;i<z;q[i]?G<<q[i]<<' ':G<<'\n',++i);
    return 0;
}