Pagini recente » Cod sursa (job #320768) | Cod sursa (job #2595821) | Romanii medaliati la IOI | Cod sursa (job #2276788) | Cod sursa (job #2527632)
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
int const NLIMIT = 100005;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M, CTC;
vector <int> Edges[NLIMIT];
vector <int> Edges_T[NLIMIT];
vector <int> Result[NLIMIT];
stack <int> S;
int Visited[NLIMIT];
void read()
{
fin >> N >> M;
for (int i = 1; i <= M; i ++)
{
int X, Y;
fin >> X >> Y;
Edges[X].push_back(Y);
Edges_T[Y].push_back(X);
}
}
void DFS(int Node)
{
Visited[Node] = 1;
for (int i = 0; i < Edges[Node].size(); i ++)
{
int Next = Edges[Node][i];
if (!Visited[Next])
DFS(Next);
}
S.push(Node);
}
void DFS_T(int Node)
{
Visited[Node] = 2;
Result[CTC].push_back(Node);
for (int i = 0; i < Edges_T[Node].size(); i ++)
{
int Next = Edges_T[Node][i];
if (Visited[Next] == 1)
DFS_T(Next);
}
}
void solve()
{
for (int i = 1; i <= N; i ++)
if (!Visited[i])
DFS(i);
while (!S.empty()) {
int V = S.top();
if (Visited[V] == 1) {
DFS_T(V);
CTC ++;
}
S.pop();
}
}
void write()
{
fout << CTC << "\n";
for (int i = 0; i < CTC; i ++) {
for (int j = 0; j < Result[i].size(); j ++)
fout << Result[i][j] << " ";
fout << "\n";
}
}
int main()
{
read();
solve();
write();
return 0;
}