Pagini recente » Cod sursa (job #194272) | Cod sursa (job #2708654) | Cod sursa (job #2676762) | Cod sursa (job #342070) | Cod sursa (job #1597878)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
#define MAXN 100005
vector <int> edge[MAXN], edgeT[MAXN], order, solution[MAXN];
int N, M;
int used[MAXN], height[MAXN];
void DF_Plus (int node)
{
used[node] = 1;
for (int i = 0; i < edge[node].size(); ++i)
if (!used[edge[node][i]])
DF_Plus(edge[node][i]);
order.push_back(node);
}
void DF_Minus (int node, int component)
{
height[node] = component;
for (int i = 0; i < edgeT[node].size(); ++i)
if (!height[edgeT[node][i]])
DF_Minus(edgeT[node][i], component);
}
int main()
{
fin >>N >>M;
for (int i = 1; i <= M; ++i)
{
int x, y;
fin >>x >>y;
edge[x].push_back(y);
edgeT[y].push_back(x);
}
for (int i = 1; i <= N; ++i)
if (!used[i])
DF_Plus(i);
int component = 1;
for (; order.size(); order.pop_back())
if (!height[order.back()])
{
DF_Minus(order.back(), component);
++component;
}
for (int i = 1; i <= N; ++i)
solution[height[i]].push_back(i);
fout <<--component <<'\n';
for (int i = 1; i <= component; ++i){
for (int j = 0; j < solution[i].size(); ++j)
fout <<solution[i][j] <<' ';
fout <<'\n';
}
return 0;
}