Pagini recente » Cod sursa (job #1876929) | Cod sursa (job #2911327) | Cod sursa (job #2520929) | Cod sursa (job #1487819) | Cod sursa (job #3335619)
#include <fstream>
#include <stack>
#include <vector>
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
class Graph {
private:
int V;
std::vector<std::vector<int>>adj;
std::vector<std::vector<int>>adjT;
std::vector<bool>viz;
std::vector<bool>vizT;
std::stack<int>st;
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) {
viz[s] = true;
for(const int& v : adj[s]) {
if(!viz[v]) dfs(v);
}
st.push(s);
}
void dfsT(int s, std::vector<int>&mmb) {
vizT[s] = true;
mmb.push_back(s);
for(const int& v : adjT[s]) {
if(!vizT[v]) dfsT(v, mmb);
}
}
void kosaraju() {
std::vector<std::vector<int>>cc;
int ccc = 0;
for(int i=1;i<=V;++i) {
if(!viz[i]) dfs(i);
}
while(!st.empty()) {
int c = st.top();
st.pop();
if(!vizT[c]) {
std::vector<int>curenta;
ccc++;
dfsT(c, curenta);
cc.push_back(curenta);
}
}
fout<<ccc<<std::endl;
for(const std::vector<int> &c : cc) {
for(int i=0;i<c.size();++i) {
fout<< c[i] << " ";
}
fout<<std::endl;
}
}
};
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.kosaraju();
return 0;
}