Pagini recente » Cod sursa (job #3293971) | Cod sursa (job #3293818) | Cod sursa (job #3291373) | Cod sursa (job #3293367) | Cod sursa (job #236181)
Cod sursa(job #236181)
// componente tare conexe O(n+m)
using namespace std;
#include <string>
#include <cstdio>
#include <vector>
#define N 100001
#define dim 8192
char ax[dim];
int pz;
inline void cit(int &x)
{
x=0;
while(ax[pz]<'0' || ax[pz]>'9')
if(++pz==dim)fread(ax,1,dim,stdin),pz=0;
while(ax[pz]>='0' && ax[pz]<='9')
{
x=x*10+ax[pz]-'0';
if(++pz==dim)fread(ax,1,dim,stdin),pz=0;
}
}
struct nod { int x; nod *n;};
nod *a[N];
nod *Ta[N];
int n,m;
int st[N];
int ns;
bool use[N];
vector<vector<int> > sol;
inline void add(int i, int j)
{
nod *p=new nod;
p->x=j;
p->n=a[i];
a[i]=p;
}
inline void add2(int i, int j)
{
nod *p=new nod;
p->x=j;
p->n=Ta[i];
Ta[i]=p;
}
void read()
{
freopen("ctc.out","w",stdout);
freopen("ctc.in","r",stdin);
cit(n);cit(m);
int p,q;
while(m--)
{
cit(p);cit(q);
add(p,q);
add2(q,p);
}
}
inline void dfs(int n)
{
use[n]=1;
for(nod *i=a[n]; i; i=i->n)
if(!use[i->x])
dfs(i->x);
st[++ns]=n;
}
inline void df(int n) // merg pe graful transpus
{
use[n]=0;
sol[sol.size()-1].push_back(n);
//printf("%d ", n);
for(nod *i=Ta[n]; i; i=i->n)
if(use[i->x])
df(i->x);
}
void solve()
{
int i;
for(i=1;i<=n;++i)
if(!use[i]) dfs(i);
vector<int>aux;
for(i=n; i ;--i)
if(use[st[i]])
{
sol.push_back(aux);
df(st[i]);
}
printf("%d\n", sol.size());
for(i=0;i<sol.size();++i)
{
for(int j=0;j<sol[i].size();++j)printf("%d ", sol[i][j]);
printf("\n");
}
}
int main()
{
read();
solve();
return 0;
}