Cod sursa(job #2391715)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 29 martie 2019 09:53:24
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include<cstdio>
#include<vector>
using namespace std;
const int N=100001,M=10000000;
vector<int> s[N],u[N],v[N];
int n,m,a[N],c,r,x,y,i,j,e=-1,l;
bool b[N];
char q[M];
inline int C()
{
  	int s=0;
  	for(e++;q[e]>='0'&&q[e]<='9';e++)
  		s=s*10+q[e]-'0';
  	return s;
}
inline void S(int x,char c)
{
    int i,d=x>999999999?10:x>99999999?9:x>9999999?8:x>999999?7: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--)
        q[l+i]=x%10+48;
    q[l+d]=c,l+=d+1;
}
inline void A(int i)
{
    if(b[i])
		return;
	int j,k;
	for(b[i]=1,k=u[i].size(),j=0;j<k;j++)
		A(u[i][j]);
    a[++c]=i;
}
inline void B(int i)
{
    if(!b[i])
		return;
	int j,k;
	for(b[i]=j=0,k=v[i].size();j<k;j++)
    	B(v[i][j]);
    s[r].push_back(i);
}
int main()
{
    freopen("ctc.in","r",stdin),freopen("ctc.out","w",stdout),fread(q,1,M,stdin),n=C(),m=C();
    while(m--)
    	x=C(),y=C(),u[x].push_back(y),v[y].push_back(x);
    for(i=1;i<=n;i++)
		A(i);
    for(i=n;i;i--)
		if(b[a[i]])
			r++,B(a[i]);
	for(S(r,'\n'),i=r;i;i--)
	{
		for(c=s[i].size(),j=0;j<c;j++)
			S(s[i][j],' ');
		q[l++]=10;
	}
	fwrite(q,1,l,stdout);
}