Pagini recente » Cod sursa (job #145555) | Cod sursa (job #1469456) | Cod sursa (job #179130) | Cod sursa (job #1615728) | Cod sursa (job #1216171)
#include<fstream>
#include<vector>
#include<cstring>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int NMAX = 100010;
vector <int> g[NMAX], gr[NMAX], Component, order, Components[NMAX];
int n,m,i,x,y,V[NMAX], cp=0;
void df1(int x)
{
V[x]=1;
int i;
for (i=0;i<g[x].size();i++)
if (!V[ g[x][i] ])
df1(g[x][i]);
order.push_back(x);
}
void df2(int x)
{
V[x]=1;
int i;
Component.push_back(x);
for (i=0;i<gr[x].size();i++)
if (!V[ gr[x][i] ])
df2(gr[x][i]);
}
int main()
{
cin>>n>>m;
while (m--)
{
cin>>x>>y;
g[x].push_back(y);
gr[y].push_back(x);
}
for (int i=1;i<=n;i++)
if (!V[i]) df1(i);
memset(V,0,sizeof V);
for (int i=n;i>0;i--)
if (!V[order[i-1]])
{
df2(order[i-1]);
++cp;
for (int j=0;j<Component.size();j++) Components[cp].push_back(Component[j]);
Component.clear();
}
cout<<cp<<"\n";
for (int i=1;i<=cp;i++)
{
for (int j=0; j<Components[i].size();j++) cout<<Components[i][j]<<" ";
cout<<"\n";
}
}