Pagini recente » Monitorul de evaluare | Cod sursa (job #447726) | Cod sursa (job #3328573) | Monitorul de evaluare | Cod sursa (job #3346572)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
vector<vector<int>> G, GT;
vector<bool> visited;
stack<int> s;
vector<int> scc;
void dfs(int node) {
visited[node] = true;
for (int next : G[node])
if (!visited[next])
dfs(next);
s.push(node);
}
void dfs2(int node, int cnt) {
visited[node] = true;
scc[node] = cnt;
for (int next : GT[node])
if (!visited[next])
dfs2(next, cnt);
}
int main() {
// ios_base :: sync_with_stdio(false);
// cin.tie(nullptr);
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m;
cin >> n >> m;
G.resize(n + 1);
GT.resize(n + 1);
visited.resize(n + 1);
scc.resize(n + 1);
for (int i = 1; i <= m; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
GT[b].push_back(a);
}
for (int i = 1; i <= n; ++i)
if (!visited[i])
dfs(i);
visited.assign(n + 1, false);
int cnt = 0;
while (!s.empty()) {
int node = s.top();
s.pop();
if (!visited[node]) {
cnt++;
dfs2(node, cnt);
}
}
vector<vector<int>> ans(cnt + 1);
for (int i = 1; i <= n; ++i)
ans[scc[i]].push_back(i);
cout << cnt << '\n';
for (int i = 1; i <= cnt; ++i, cout << '\n')
for (int node : ans[i])
cout << node << ' ';
return 0;
}