Pagini recente » Clasamentul arhivei educationale | Cod sursa (job #3293360) | Cod sursa (job #3291873) | Cod sursa (job #3293836) | Cod sursa (job #236171)
Cod sursa(job #236171)
// 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];
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;
}
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);
}
}
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)
{
use[n]=0;
sol[sol.size()-1].push_back(n);
//printf("%d ", n);
for(nod *i=a[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[i])
{
sol.push_back(aux);
df(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;
}