Pagini recente » Cod sursa (job #2684911) | Cod sursa (job #1800053) | Cod sursa (job #2029566) | Cod sursa (job #1481231) | Cod sursa (job #1193368)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
#define ech(It, A) for (__typeof(A.begin()) It = A.begin(); It != A.end(); ++It)
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
vector<vector<int> > adjl;
vector<int> dfs_num;
vector<int> dfs_low;
vector<int> scc_num;
vector<vector<int> > scc;
stack<int> dfs_stack;
int dfs_cnt = 1;
int scc_cnt = 1;
void dfs(int u) {
dfs_low[u] = dfs_num[u] = dfs_cnt++;
dfs_stack.push(u);
ech(it, adjl[u]) {
if (scc_num[*it] != 0) continue;
if (dfs_num[*it] != 0) {
dfs_low[u] = min( dfs_low[u], dfs_low[*it] );
}
else {
dfs(*it);
dfs_low[u] = min( dfs_low[u], dfs_low[*it] );
}
}
if (dfs_low[u] == dfs_num[u]) {
while (dfs_stack.top() != u) {
scc_num[dfs_stack.top()] = scc_cnt;
dfs_stack.pop();
}
scc_num[dfs_stack.top()] = scc_cnt;
dfs_stack.pop();
scc_cnt++;
}
}
void tarjan_scc() {
dfs_num.resize(n+1);
dfs_low.resize(n+1);
scc_num.resize(n+1);
for (int i = 1; i <= n; ++i) {
if (scc_num[i] == 0) dfs(i);
}
scc.resize(scc_cnt--);
for (int i = 1; i <= n; ++i) {
scc[scc_num[i]].push_back(i);
}
}
int main() {
fin >> n >> m;
adjl.resize(n+1);
for (int i = 0; i < m; ++i) {
int u, v;
fin >> u >> v;
adjl[u].push_back(v);
}
tarjan_scc();
fout << scc_cnt << '\n';
for (int i = 1; i <= scc_cnt; ++i) {
ech(it, scc[i]) {
fout << *it << ' ';
}
fout << '\n';
}
return 0;
}