Pagini recente » Cod sursa (job #1728770) | Cod sursa (job #616418) | Cod sursa (job #1183629) | Cod sursa (job #1313049) | Cod sursa (job #3252941)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int>st;
vector<bool>viz;
vector<vector<int>>ctc;
//void dfs2(int node, vector<vector<int>>&edges, vector<int>&add_to) {
// viz[node]=1;
// for (auto newnode:edges[node]) {
// int newnode=edges[node][i];
// if (!viz[newnode]) {
// dfs(noewnode, edges);
// }
// }
// add_to.push_back(node);
//}
void dfs(int node, vector<vector<int>>&edges, vector<int>&add_to) {
viz[node]=1;
for (auto it:edges[node]) {
if (viz[it]==0) dfs(it, edges, add_to);
}
add_to.push_back(node);
}
void Solve() {
int n, m; fin>>n>>m;
vector<vector<int>>edges(n);
vector<vector<int>>rev_edges(n);
for (int i=0; i<m; i++) {
int a, b;
fin>>a>>b;
a--;
b--;
edges[a].push_back(b);
rev_edges[b].push_back(a);
}
viz.resize(n);
vector<int>st;
for (int node=0; node<n; node++) {
if (!viz[node]) dfs(node, edges, st);
}
viz.clear();
viz.resize(n);
vector<vector<int>>ctc;
for (int i=st.size()-1; i>=0; i--) {
if (viz[st[i]]==0) {
ctc.push_back(vector<int>());
dfs(st[i], rev_edges, ctc.back());
}
}
fout<<ctc.size()<<'\n';
for (auto comp:ctc) {
for (auto node:comp) {
fout<<node+1<<' ';
}
fout<<'\n';
}
}
int main()
{
Solve();
return 0;
}