Pagini recente » Cod sursa (job #2544627) | Cod sursa (job #819027) | Cod sursa (job #1795652) | Cod sursa (job #2103686) | Cod sursa (job #3036863)
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
typedef long long ll;
typedef pair<int, int> pi;
int t, T;
int elapsed_time = 0;
void DFS(int node, vector<vector<int>>& edges, vector<int>& finish, vector<int>& visited) {
elapsed_time++;
visited[node] = 1;
for(int neigh: edges[node])
if (!visited[neigh]) {
DFS(neigh, edges, finish, visited);
}
visited[node] = 2;
elapsed_time++;
finish[node] = elapsed_time;
}
void BFS(int start_node, vector<vector<int>>& edges, vector<int>& visited, vector<vector<int>>& answers) {
answers.push_back(vector<int>{});
queue<int> qu;
visited[start_node] = 1;
qu.push(start_node);
while (!qu.empty()) {
int node = qu.front();
qu.pop();
visited[node] = 2;
answers.back().push_back(node);
for(int neigh: edges[node])
if (!visited[neigh]) {
visited[neigh] = 1;
qu.push(neigh);
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
f >> n >> m;
vector<vector<int>> V(n + 1), VT(n + 1);
for (int i = 0; i < m; i++) {
int a, b;
f >> a >> b;
V[a].push_back(b);
VT[b].push_back(a);
}
vector<int> visited(n + 1, 0), finish(n + 1, 0);
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
DFS(i, V, finish, visited);
}
}
vector<pi> top;
for (int i = 1; i <= n; i++) {
top.push_back({ i, finish[i] });
}
sort(top.begin(), top.end(), [](const pi& X, const pi& Y) {
return X.second >= Y.second;
});
top.resize(top.size());
for (int i = 1; i <= n; i++) {
visited[i] = 0;
}
vector<vector<int>> answers;
for (int i = 0; i < top.size(); i++) {
if (!visited[top[i].first]) {
BFS(top[i].first, VT, visited, answers);
}
}
g << answers.size() << '\n';
for (vector<int>& component : answers) {
for (int node : component)
g << node << ' ';
g << '\n';
}
return 0;
}