Cod sursa(job #2421113)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 14 mai 2019 12:24:02
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define N 100001
#define P 15000000
int n,m,i,o,k,x,y,l[N],s[N],c[N],u=-1,w;
vector<int> v[N],t[N];
char r[P];
inline int A()
{
  	int s=0;
  	for(u++;r[u]>47;u++)
  		s=s*10+r[u]-48;
  	return s;
}
inline void S(int x)
{
    int i,d=x>99999?6:x>9999?5:x>999?4:x>99?3:x>9?2:1;
    for(i=d-1;i>=0;x/=10,i--)
        r[w+i]=x%10+48;
    w+=d;
}
inline void D(int x)
{
    int z;
    s[++k]=x;
    for(auto i:v[x])
        if(!l[i])
        {
            z=k,l[i]=c[i]=c[x]+1,D(i),l[x]=min(l[x],l[i]);
            if(l[i]>=c[x])
            {
                for(o++;k>z;t[o].pb(s[k--]));
                t[o].pb(x);
            }
        }
        else
            l[x]=min(l[x],c[i]);
}
int main()
{
    freopen("biconex.in","r",stdin),freopen("biconex.out","w",stdout),fread(r,1,P,stdin),n=A(),m=A();
    while(m--)
        x=A(),y=A(),v[x].pb(y),v[y].pb(x);
    for(l[1]=c[1]=1,D(1),S(o),r[w++]=10,i=1;i<=o;i++,r[w++]=10)
        for(auto j:t[i])
            S(j),r[w++]=32;
    fwrite(r,1,w,stdout);
}