Pagini recente » Cod sursa (job #2088829) | Cod sursa (job #2275179) | Cod sursa (job #2226899) | Cod sursa (job #1641637) | Cod sursa (job #901829)
Cod sursa(job #901829)
#include<cstdio>
#include<vector>
#define INF 100001
using namespace std;
bool used1[INF],used2[INF];
vector<int> graph1[INF],graph2[INF];
vector<int> Q;
vector<int> ras[INF];
int n,m,nr=0;
void df1(int nod)
{
if(used1[nod])return;
used1[nod]=1;
for(int i=0;i<graph1[nod].size();++i)
{
int nod2=graph1[nod][i];
df1(nod2);
}
Q.push_back(nod);
}
void df2(int nod)
{
if(used2[nod])return;
used2[nod]=1;
ras[nr].push_back(nod);
for(int i=0;i<graph2[nod].size();++i)
df2(graph2[nod][i]);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
graph1[x].push_back(y);
graph2[y].push_back(x);
}
for(int i=1;i<=n;++i)
if(!used1[i])df1(i);
while(Q.size()>0)
{
int nod=Q.back();
if(!used2[nod])
{
++nr;
df2(nod);
}
Q.pop_back();
}
printf("%d\n",nr);
for(int i=1;i<=nr;++i)
{
for(int j=0;j<ras[i].size();++j)printf("%d ",ras[i][j]);
printf("\n");
}
return 0;
}