Pagini recente » Cod sursa (job #803950) | Cod sursa (job #23566) | Cod sursa (job #1211071) | Cod sursa (job #1361566) | Cod sursa (job #3337252)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
class Graph {
int V;
std::vector<std::vector<int>>adj;
std::vector<std::vector<int>>adjT;
std::vector<int>vizT;
std::vector<int>viz;
public:
Graph(int n) {
V = n;
adj.resize(V+1);
adjT.resize(V+1);
viz.resize(V+1, false);
vizT.resize(V+1, false);
}
void addEdge(int x, int y) {
adj[x].push_back(y);
adjT[y].push_back(x);
}
void dfs(int s, std::stack<int>& st) {
viz[s] = true;
for(auto& v : adj[s]) {
if(!viz[v]) {
dfs(v, st);
}
}
st.push(s);
}
void dfsT(int s, std::vector<int>&comp) {
vizT[s] = true;
comp.push_back(s);
for(auto& v : adjT[s]) {
if(!vizT[v]) {
dfsT(v, comp);
}
}
}
void proc() {
std::stack<int>st;
std::vector<std::vector<int>>cc;
for(int i=1;i<=V;++i) {
if(!viz[i]) {
dfs(i, st);
}
}
int counter = 0;
while(!st.empty()) {
int c = st.top();
st.pop();
if(!vizT[c]) {
counter++;
std::vector<int>comp;
dfsT(c, comp);
cc.push_back(comp);
}
}
fout<<counter<<'\n';
for(auto& elem : cc) {
for(auto& e : elem) {
fout<<e<<' ';
}
fout<<'\n';
}
}
};
int main(void) {
int n, m, x, y;
fin >> n >> m;
Graph g(n);
for(int i=1;i<=m;++i) {
fin >> x >> y;
g.addEdge(x, y);
}
g.proc();
return 0;
}