Pagini recente » Cod sursa (job #3170939) | Cod sursa (job #181276) | Cod sursa (job #2990172) | Cod sursa (job #1353206) | Cod sursa (job #3149809)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int NODES_MAX = 1e5;
vector<int> edge[NODES_MAX];
vector<int> revEdge[NODES_MAX];
vector<int> stronglyConnectedComponents[NODES_MAX];
vector<int> orderStack;
bool marked[NODES_MAX];
inline void addEdge(int u, int v){
edge[u].push_back(v);
revEdge[v].push_back(u);
}
template<typename T>
void reset(T v[], int n, T val){
for(int i = 0; i < n; ++i)
v[i] = val;
}
void dfs(const int& node, const vector<int>* edge, vector<int>& visited){
marked[node] = true;
for(auto neighbour: edge[node])
if(!marked[neighbour])
dfs(neighbour, edge, visited);
visited.push_back(node);
}
int main(){
int nodes, edges, u, v;
fin >> nodes >> edges;
for(int i = 0; i < edges; ++i){
fin >> u >> v;
addEdge(u - 1, v - 1);
}
for(int node = 0; node < nodes; ++node)
if(!marked[node])
dfs(node, edge, orderStack);
reset(marked, nodes, false);
int noSCC = 0;
while(!orderStack.empty()){
int node = orderStack.back();
orderStack.pop_back();
if(!marked[node]){
dfs(node, revEdge, stronglyConnectedComponents[noSCC]);
++noSCC;
}
}
fout << noSCC << '\n';
for(int i = 0; i < noSCC; ++i){
for(auto x: stronglyConnectedComponents[i])
fout << x + 1 << ' ';
fout.put('\n');
}
fin.close();
fout.close();
return 0;
}