Pagini recente » Cod sursa (job #2559870) | Cod sursa (job #478008) | Cod sursa (job #1098661) | Cod sursa (job #928685) | Cod sursa (job #2758647)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
// Tarjan
void dfs(int node, int& index, vector<int>& idx, vector<int>& lowlink, vector<bool>& instack, stack<int>& DFS, const vector<vector<int>>& graph, vector<vector<int>>& components){
idx[node] = lowlink[node] = ++index;
DFS.push(node);
instack[node] = true;
for(auto adjacent : graph[node]){
if(idx[adjacent] == -1){
dfs(adjacent, index, idx, lowlink, instack, DFS, graph, components);
lowlink[node] = min(lowlink[node], lowlink[adjacent]);
}
else if(instack[adjacent]){
lowlink[node] = min(lowlink[node], lowlink[adjacent]);
}
}
if(idx[node] == lowlink[node]){
components.push_back({});
int current;
do{
current = DFS.top();
components[components.size() - 1].push_back(current);
instack[current] = false;
DFS.pop();
}while(current != node);
}
}
int main()
{
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int N, M;
cin >> N >> M;
vector<vector<int>> graph;
vector<int> idx, lowlink;
vector<bool> instack;
for(int i = 0; i < N; ++i){
graph.push_back({});
idx.push_back(-1);
lowlink.push_back(-1);
instack.push_back(false);
}
for(int x, y; M > 0; --M){
cin >> x >> y;
--x; --y;
graph[x].push_back(y);
}
vector<vector<int>> components;
int index = 0;
for(int i = 0; i < N; ++i)
if(idx[i] == -1){
stack<int> DFS;
dfs(i, index, idx, lowlink, instack, DFS, graph, components);
}
cout << components.size() << "\n";
for(auto component : components){
for(auto component_member : component)
cout << component_member + 1 << " ";
cout << "\n";
}
cin.close();
cout.close();
return 0;
}