Cod sursa(job #1791686)

Utilizator Kln1000Ciobanu Bogdan Kln1000 Data 29 octombrie 2016 17:08:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");ofstream t("ctc.out");
struct A{int ix,l;bool u=1,r=0;vector<int>y;};
int n,m,b=0;vector<int>q;vector<vector<int> >s;vector<A>v(100010);
void d(int x){v[x].u=0,v[x].ix=v[x].l=b++,q.push_back(x),v[x].r=1;
for (auto i:v[x].y)if(v[i].u)d(i),v[x].l=min(v[x].l,v[i].l);else if (v[i].r)v[x].l=min(v[x].l,v[i].l);
if (v[x].l==v[x].ix){int a;vector<int>k;
do a=q.back(),q.pop_back(),k.push_back(a),v[a].r=0;
while(a!=x);s.push_back(k);}}
main()
{int x,y;f>>n>>m;
for (int i=0;i<m;++i)
f>>x>>y,v[x-1].y.push_back(y-1);
for (int i=0;i<n;++i)if (v[i].u)d(i);
t<<s.size()<<'\n';
for(int i=0;i<s.size();++i){
for (int j=0;j<s[i].size();++j)
t<<1+s[i][j]<<" ";t<<'\n';}}