Pagini recente » Cod sursa (job #2666335) | Cod sursa (job #1347695) | Cod sursa (job #2405436) | Cod sursa (job #2727009) | Cod sursa (job #3203155)
#include <bits/stdc++.h>
#define MAXN 100000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
vector<vector<int>> graph;
vector<vector<int>> tgraph;
bitset<MAXN> visited;
void dfs(vector<vector<int>>& graph, int node, bitset<MAXN>& fr) {
for (auto& neighbour: graph[node])
if (!fr[neighbour]) {
fr[neighbour] = true;
dfs(graph, neighbour, fr);
}
}
int main() {
fin >> n >> m;
graph = vector<vector<int>>(n, vector<int>());
tgraph = vector<vector<int>>(n, vector<int>());
for (int i = 0; i < m; i++) {
int from, to;
fin >> from >> to;
from--, to--;
graph[from].push_back(to);
tgraph[to].push_back(from);
}
vector<vector<int>> solutions;
for (int i = 0; i < n; i++) {
if (visited[i])
continue;
bitset<MAXN> gvisited;
bitset<MAXN> tvisited;
dfs(graph, i, gvisited);
dfs(tgraph, i, tvisited);
solutions.emplace_back();
for (int i = 0; i < n; i++)
if (gvisited[i] && tvisited[i]) {
solutions[solutions.size() - 1].push_back(i + 1);
visited[i] = true;
}
}
fout << solutions.size() << '\n';
for (auto& sol: solutions) {
for (auto& node: sol)
fout << node << ' ';
fout << '\n';
}
return 0;
}