Pagini recente » Cod sursa (job #236448) | Cod sursa (job #2413645) | Cod sursa (job #1282457) | Cod sursa (job #797072) | Cod sursa (job #2969883)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int V, E;
vector<vector<int>> adjList, adjListTrans;
vector<bool> visited;
stack<int> stk;
void init(){
adjList.resize(V+1);
adjListTrans.resize(V+1);
visited.resize(V+1);
}
void read() {
in >> V >> E;
init();
for(int i = 0; i < E; i++){
int u, v;
in >> u >> v;
adjList[u].push_back(v);
adjListTrans[v].push_back(u);
}
}
void print(const vector<vector<int>>& SCCs){
out << SCCs.size() << '\n';
for(const auto & scc: SCCs){
for(auto u: scc)
out << u << ' ';
out << '\n';
}
}
void first_dfs(int u){
visited[u] = true;
for(auto v: adjList[u]){
if(!visited[v])
first_dfs(v);
}
stk.push(u);
}
void second_dfs(int u, vector<int>& scc){
visited[u] = true;
scc.push_back(u);
for(auto v: adjListTrans[u]){
if(!visited[v])
second_dfs(v, scc);
}
}
void kosaraju(){
for(int i = 1; i <= V; i++){
if(!visited[i])
first_dfs(i);
}
fill(visited.begin(), visited.end(), false);
vector<vector<int>> SCCs; // Strongly Connected Components
while(!stk.empty()){
int u = stk.top();
stk.pop();
if(!visited[u]){
vector<int> scc = {};
second_dfs(u, scc);
SCCs.push_back(scc);
}
}
print(SCCs);
}
int main() {
read();
kosaraju();
return 0;
}