Cod sursa(job #2390886)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 28 martie 2019 13:58:03
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 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];
int A()
{
  	int s=0;
  	for(u++;r[u]>='0'&&r[u]<='9';u++)
  		s=s*10+r[u]-'0';
  	return s;
}
void S(int x,char c)
{
    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;
    r[w+d]=c,w+=d+1;
}
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);
    l[1]=c[1]=1,D(1),S(o,'\n');
    for(i=1;i<=o;i++,r[w++]="\n")
        for(auto j:t[i])
            S(j,' ');
    fwrite(r,1,w,stdout);
}