Pagini recente » Cod sursa (job #1455574) | Cod sursa (job #3294360)
#include <bits/stdc++.h>
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
//#define fin std::cin
//#define fout std::cout
const int NMAX = 1e5 + 5;
int n, m;
std::vector<int> G[NMAX];
int curr_idx = 1; // id-ul folosit pt asocieri
int idx[NMAX]; // id-ul nodului
int lowlink[NMAX]; // cel mai mic idx la care pot ajunge
bool on_stack[NMAX]; // activ in stiva
std::stack<int> st;
int ctc_cnt;
std::vector<int> ctc[NMAX];
void dfs(int node)
{
idx[node] = curr_idx++; // ii dam id-ul nodului
lowlink[node] = idx[node]; // idx-ul minim este id-ul nodului la inceput
on_stack[node] = true; // bag nodul in stiva, o sa faca parte dintr-un CTC nou
st.push(node);
for(auto adj : G[node])
if(!idx[adj]) // nu l-am parcurs in dfs
{
dfs(adj);
lowlink[node] = std::min(lowlink[node], lowlink[adj]);
}
else if(on_stack[adj]) // am mai trecut, dar inca nu face parte dintr-un CTC
lowlink[node] = std::min(lowlink[node], lowlink[adj]);
if(lowlink[node] == idx[node]) // parcurgand CTC-ul eu tot aici vreau sa ma intorc, este un ciclu bidirectional
{
ctc_cnt++;
int curr_node;
do {
// am CTC-ul, il scot din stiva
curr_node = st.top();
st.pop();
ctc[ctc_cnt].push_back(curr_node);
on_stack[curr_node] = false;
} while(curr_node != node);
}
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= m; ++i)
{
int x, y;
fin >> x >> y;
G[x].push_back(y);
}
// idx[i] = 0 <=> nu am vizitat nodul
for(int i = 1; i <= n; ++i)
if(!idx[i])
dfs(i);
// doar le afisez acum
fout << ctc_cnt << "\n";
for(int i = 1; i <= ctc_cnt; ++i, fout << "\n")
for(auto node : ctc[i])
fout << node << " ";
return 0;
}