Pagini recente » Cod sursa (job #1966837) | Cod sursa (job #2610771) | Cod sursa (job #2790277) | Cod sursa (job #524014) | Cod sursa (job #2784804)
// TARJAN IMPLEMENTATION
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int> la[100000];
stack<int> st;
int onStack[100000];
int ids[100000];
int lowLink[100000];
int id = 0;
int ctc = 0;
vector<vector<int>> ctcV;
int n,m;
void dfs(int nod)
{
st.push(nod);
onStack[nod] = 1;
ids[nod] = id;
lowLink[nod] = id;
id ++;
for (auto& el: la[nod])
{
if (ids[el] == -1)
dfs(el);
if (onStack[el])
{
lowLink[nod] = min(lowLink[nod], lowLink[el]);
}
}
if (ids[nod] == lowLink[nod])
{
ctcV.push_back(vector<int>());
int nod_curent = st.top();
st.pop();
ctcV[ctc].push_back(nod_curent);
while (nod_curent != nod)
{
onStack[nod_curent] = 0;
nod_curent = st.top();
st.pop();
ctcV[ctc].push_back(nod_curent);
}
ctc++;
}
}
int main()
{
in >> n >> m;
for (int i = 0; i < n; i++)
ids[i] = -1;
for (int i = 0; i < m; ++i)
{
int n1, n2;
in >> n1 >> n2;
la[n1-1].push_back(n2-1);
}
for (int i = 0; i < n; i++)
{
if (ids[i] == -1)
dfs(i);
}
out << ctc << '\n';
for (auto& rand: ctcV)
{
for (auto& el: rand)
out << el+1 << ' ';
out << '\n';
}
return 0;
}