Pagini recente » Cod sursa (job #2081000) | Cod sursa (job #843620) | Cod sursa (job #1517493) | Cod sursa (job #1027701) | Cod sursa (job #3210462)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int MAXN = 1e5;
vector<int> G[MAXN + 1];
vector<int> idx;
vector<int> lowlink;
vector<bool> viz;
vector<bool> check;
stack<int> st;
int N, M, GIDX;
vector <vector <int>> sol;
void tarjan(int node) {
++GIDX;
st.emplace(node);
check[node] = 1;
viz[node] = 1;
idx[node] = GIDX;
lowlink[node] = GIDX;
for ( const auto& vecin: G[node]) {
if (!viz[vecin] ) {
tarjan(vecin);
lowlink[node] = min(lowlink[node], lowlink[vecin]);
}
else {
if ( check[vecin] ) {
lowlink[node] = min(lowlink[node], idx[vecin]);
}
}
}
if ( lowlink[node] == idx[node] ) {
int top;
vector <int> ctc;
do {
top = st.top();
st.pop();
check[top] = 0;
ctc.emplace_back(top);
}
while ( top != node);
sol.emplace_back(ctc);
}
}
int main() {
fin >> N >> M;
idx.resize(N + 1);
lowlink.resize(N + 1);
viz.resize(N + 1, false);
check.resize(N + 1, false);
int x, y;
while(M--) {
fin >> x >> y;
G[x].push_back(y);
}
for ( int i = 1; i <= N; ++ i) {
if ( !viz[i] ) {
tarjan(i);
}
}
fout << sol.size() << '\n';
for ( const auto& comp: sol) {
for ( const auto& elem: comp ) {
fout << elem << " ";
}
fout << '\n';
}
}