Pagini recente » Cod sursa (job #3219297) | Cod sursa (job #2932256) | Cod sursa (job #513202) | Cod sursa (job #2761319) | Cod sursa (job #2898127)
#include <iostream>
#include <vector>
#include <stack>
#define NMAX 100005
using namespace std;
stack<int> sk;
int viz[NMAX];
vector<int> adj[NMAX];
vector<int> rev_adj[NMAX];
int N, M;
void DFS_K(int node)
{
viz[node] = 1;
for (int i = 0; i < adj[node].size(); i++) {
if (!viz[adj[node][i]])
DFS_K(adj[node][i]);
}
sk.push(node);
}
int ans;
vector<int> comps;
void DFS_K2(int node)
{
viz[node] = 1;
comps.push_back(node);
for (int i = 0; i < rev_adj[node].size(); i++) {
if (!viz[rev_adj[node][i]])
DFS_K2(rev_adj[node][i]);
}
}
void Kosaraju()
{
for (int i = 1; i <= N; i++)
viz[i] = 0;
// DFS through the graph and add to a stack nodes when they don't have any unvisited neighbours.
for (int i = 1; i <= N; i++)
if (!viz[i])
DFS_K(i);
for (int i = 1; i <= N; i++)
viz[i] = 0;
// DFS through the transpose matrix from the nodes in the stack.
while (!sk.empty())
{
if (!viz[sk.top()]) {
DFS_K2(sk.top());
comps.push_back(-1);
ans++;
}
sk.pop();
}
cout << ans << '\n';
for (int j = 0; j < comps.size(); j++)
if (comps[j] != -1)
cout << comps[j] << " ";
else
cout << '\n';
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
cin >> N >> M;
int node1, node2;
for (int i = 1; i <= M; i++) {
cin >> node1 >> node2;
adj[node1].push_back(node2);
rev_adj[node2].push_back(node1);
}
Kosaraju();
return 0;
}