Pagini recente » Cod sursa (job #533103) | Cod sursa (job #34511) | Cod sursa (job #768425) | Cod sursa (job #2780787) | Cod sursa (job #1442554)
#include<fstream>
#include<vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
const int NMAX = 100004;
int N, M, i,j,x,y, NR;
vector<int> g[NMAX], gr[NMAX], scc[NMAX];
vector<int> used(NMAX,0), order;
void dfs1(int v)
{
used[v]=1;
for (int i=0;i<g[v].size();i++)
if (!used[g[v][i]]) dfs1(g[v][i]);
order.push_back(v);
}
void dfs2(int v)
{
used[v]=1;
scc[NR].push_back(v);
for(int i=0;i<gr[v].size();i++)
if (!used[gr[v][i]]) dfs2(gr[v][i]);
}
int main()
{
cin >> N >> M;
while (M--)
{
cin >> x >> y;
g[x]. push_back(y);
gr[y].push_back(x);
}
for (i=1;i<=N;i++)
if (!used[i]) dfs1(i);
used.assign(N+1,0);
for (i=N-1;i>=0;i--)
if (!used[order[i]])
{
++NR;
dfs2(order[i]);
}
cout << NR << '\n';
for (i=1;i<=NR;i++)
{
for (j=0;j<scc[i].size();j++)cout<<scc[i][j]<<' ';
cout<<'\n';
}
return 0;
}