Pagini recente » Cod sursa (job #588521) | Cod sursa (job #1005292) | Cod sursa (job #239590) | Cod sursa (job #2783765) | Cod sursa (job #2971807)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
constexpr size_t LIM = 100005;
int N, M, node1, node2, i;
vector<int> G[LIM], GT[LIM];
vector<vector<int>> scc;
bool vis[LIM], vis_t[LIM];
stack<int> st;
static void dfs1(int node) {
vis[node] = true;
for (const int adj : G[node])
if (!vis[adj]) dfs1(adj);
st.push(node);
}
static void dfs2(int node) {
vis_t[node] = true;
scc.back().push_back(node);
for (const int adj : GT[node])
if (!vis_t[adj]) dfs2(adj);
}
int main() {
fin >> N >> M;
for (i = 1; i <= M; ++i) {
fin >> node1 >> node2;
G[node1].push_back(node2);
GT[node2].push_back(node1);
}
for (i = 1; i <= N; ++i)
if (!vis[i]) dfs1(i);
while (!st.empty()) {
const int node = st.top();
if (!vis_t[node]) {
scc.emplace_back();
dfs2(node);
}
st.pop();
}
fout << scc.size() << '\n';
for (const auto& component : scc) {
for (const int node : component)
fout << node << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}