Pagini recente » Cod sursa (job #527492) | Cod sursa (job #2737417) | Cod sursa (job #322293) | Cod sursa (job #3201182) | Cod sursa (job #1736906)
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX_N = 100000 + 1;
vector<int> G[MAX_N];
vector<int> GT[MAX_N];
vector<int> topsort;
bool visited[MAX_N];
vector<vector<int>> scc;
int N, M;
void dfs(int node)
{
visited[node] = true;
for (int v : G[node])
if (!visited[v])
dfs(v);
topsort.push_back(node);
}
void dfsT(int node)
{
visited[node] = false;
for (int v : GT[node])
if (visited[v])
dfsT(v);
scc.back().push_back(node);
}
void StronglyConnectedComponents()
{
for (int i = 1; i <= N; ++i)
if (!visited[i])
dfs(i);
reverse(topsort.begin(), topsort.end());
for (int node : topsort)
{
if (visited[node])
{
scc.push_back({});
dfsT(node);
}
}
}
int main()
{
ifstream in("ctc.in");
ofstream out("ctc.out");
in >> N >> M;
for (int i = 1; i <= M; ++i)
{
int a, b;
in >> a >> b;
G[a].push_back(b);
GT[b].push_back(a);
}
StronglyConnectedComponents();
out << scc.size() << "\n";
for (auto v : scc)
{
for (int x : v)
out << x << " ";
out << "\n";
}
return 0;
}