Pagini recente » Cod sursa (job #461287) | Cod sursa (job #28391) | Cod sursa (job #1274264) | Cod sursa (job #1331727) | Cod sursa (job #2424376)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int N, M, nrSol;
map<int, vector<int>> G, T, result;
map<int, bool> visited;
stack<int> tmp;
void Read()
{
fin >> N >> M;
for (int i = 0; i < M; i++)
{
int x, y;
fin >> x >> y;
G[x].push_back(y);
T[y].push_back(x);
}
}
void DFS1(int node)
{
visited[node] = true;
for (auto child : G[node])
if (!visited[child])
DFS1(child);
tmp.push(node);
}
void DFS2(int node)
{
result[nrSol].push_back(node);
visited[node] = true;
for (auto child : T[node])
if (!visited[child])
DFS2(child);
}
int main()
{
Read();
for (int i = 1; i <= N; i++)
if (!visited[i])
DFS1(i);
for (int i = 1; i <= N; i++)
visited[i] = false;
while (!tmp.empty())
{
int top = tmp.top();
if (!visited[top])
{
nrSol++;
DFS2(top);
}
tmp.pop();
}
fout << nrSol << "\n";
for (int i = 1; i <= nrSol; i++)
{
for (auto r : result[i])
fout << r << " ";
fout << "\n";
}
return 0;
}