Pagini recente » Cod sursa (job #3291507) | Cod sursa (job #3287033) | Cod sursa (job #3293363) | Cod sursa (job #3287414)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int INF = 1000*1000*1000;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
bool in_stack[100001] = {};
vector<int> disc(100001, INF);
vector<int> low(100001, INF);
stack<int> st;
vector<vector<int>> comps;
int time = 1;
void DFS_tarjan(int node, vector<vector<int>> &adj)
{
disc[node] = time;
low[node] = disc[node];
time++;
st.push(node);
in_stack[node] = true;
for(int i = 0; i < adj[node].size(); i++){
int newNode = adj[node][i];
if(disc[newNode] == INF){
DFS_tarjan(newNode, adj);
low[node] = min(low[node], low[newNode]);
}
else if(in_stack[newNode]){
low[node] = min(low[node], disc[newNode]);
}
}
if(low[node] == disc[node]){
vector<int> comp;
int curr_node = st.top();
comp.push_back(curr_node);
st.pop();
in_stack[curr_node] = false;
while(curr_node != node){
curr_node = st.top();
comp.push_back(curr_node);
st.pop();
in_stack[curr_node] = false;
}
comps.push_back(comp);
}
}
int main()
{
int N, M;
fin >> N >> M;
vector<vector<int>> adj(N+1);
for(int i = 0; i < M; i++){
int a, b;
fin >> a >> b;
adj[a].push_back(b);
}
for(int i = 1; i <= N; i++){
if(disc[i] == INF){
DFS_tarjan(i, adj);
}
}
fout << comps.size() << endl;
for(int i = 0; i < comps.size(); i++){
for(int j = 0; j < comps[i].size(); j++){
fout << comps[i][j] << " ";
}
fout << endl;
}
return 0;
}