Pagini recente » Cod sursa (job #2671065) | Cod sursa (job #2244649) | Cod sursa (job #415996) | Cod sursa (job #1499523) | Cod sursa (job #2926651)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
#define cin f
#define cout g
vector<vector<int>> adj, trans;
stack<int> st;
vector<bool> visited;
void topoSort(int currNode) {
visited[currNode] = 1;
for (int x : adj[currNode])
if (!visited[x])
topoSort(x);
st.push(currNode);
}
void DFS(int currNode, vector<int> &sol) {
visited[currNode] = 1;
for (int x : trans[currNode])
if (!visited[x])
DFS(x, sol);
sol.push_back(currNode);
}
int main() {
int n, m;
cin >> n >> m;
adj.resize(n+1);
trans.resize(n+1);
visited.resize(n+1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
trans[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (!visited[i])
topoSort(i);
fill(visited.begin(), visited.end(), 0);
int countCTC = 0;
vector<vector<int>> finalSol;
while (!st.empty()) {
int currNode = st.top();
st.pop();
if (!visited[currNode]) {
countCTC++;
vector<int> sol;
DFS(currNode, sol);
finalSol.push_back(sol);
}
}
cout << countCTC << '\n';
for (auto vec : finalSol) {
for (int x : vec)
cout << x << " ";
cout << '\n';
}
return 0;
}