Pagini recente » Cod sursa (job #134176) | Cod sursa (job #1214854) | Cod sursa (job #989176) | Cod sursa (job #388447) | Cod sursa (job #2312077)
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
vector < int > v[100002],vt[100002],l;
bool mark[100002];
void dfs(int node)
{
if(mark[node])
return;
mark[node]=1;
for(int i=0;i<v[node].size();i++)
{
vt[v[node][i]].push_back(node);
dfs(v[node][i]);
}
l.push_back(node);
}
void dfs_assign(int node, int root)
{
if(mark[node])
return;
mark[node]=1;
v[root].push_back(node);
for(int i=0;i<vt[node].size();i++)
{
dfs_assign(vt[node][i],root);
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m; f>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y; f>>x>>y;
v[x].push_back(y);
}
for(int i=1;i<=n;i++)
{
dfs(i);
}
memset(mark,0,sizeof(mark));
for(int i=1;i<=n;i++)
v[i].clear();
int nr=0;
for(int i=1;i<=n;i++)
{
dfs_assign(i,i);
}
for(int i=1;i<=n;i++)
if(v[i].size())
nr++;
g<<nr<<'\n';
for(int i=1;i<=n;i++)
if(v[i].size())
{
for(int j=0;j<v[i].size();j++)
g<<v[i][j]<<" ";
g<<'\n';
}
return 0;
}