Pagini recente » Cod sursa (job #2748480) | Cod sursa (job #3255096) | Cod sursa (job #2579911) | Cod sursa (job #761090) | Cod sursa (job #2174917)
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int Maxn=100001;
vector <int>g[Maxn],t[Maxn],comp[Maxn];
int v[Maxn],st[Maxn],vf,co;
bool viz[Maxn];
void dfs(int nod)
{
viz[nod]=true;
for(size_t i=0;i<g[nod].size();i++)
if(!viz[g[nod][i]])
dfs(g[nod][i]);
st[++vf]=nod;
}
void dfstrans(int nod)
{
viz[nod]=true;
comp[co].push_back(nod);
for(size_t i=0;i<t[nod].size();i++)
if(!viz[t[nod][i]])
dfstrans(t[nod][i]);
}
inline bool cmp(int x,int y)
{
return comp[v[x]][0]<comp[v[y]][0];
}
int main()
{
FILE *fin,*fout;
fin=fopen("ctc.in","r");
fout=fopen("ctc.out","w");
int n,m,x,y;
fscanf(fin,"%d%d",&n,&m);
for(int i=0;i<m;i++)
{
fscanf(fin,"%d%d",&x,&y);
g[x].push_back(y);
t[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!viz[i])
dfs(i);
memset(viz,false,sizeof(viz));
while(vf)
{
x=st[vf--];
if(!viz[x])
{
dfstrans(x);
sort(comp[co].begin(),comp[co].end());
v[co]=co;co++;
}
}
sort(v,v+co,cmp);
fprintf(fout,"%d\n",co);
for(int i=0;i<co;i++)
{
x=v[i];
for(size_t j=0;j<comp[x].size();j++)
fprintf(fout,"%d ",comp[x][j]);
fputc('\n',fout);
}
fclose(fin);
fclose(fout);
return 0;
}