Pagini recente » Cod sursa (job #2329563) | Cod sursa (job #412571) | Cod sursa (job #2404528) | Cod sursa (job #2533479) | Cod sursa (job #2929248)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5;
vector<vector<int>> dx(nmax+5);
int idx[nmax+5], lowlink[nmax+5], timer = 0;
stack<int> st;
bool onstack[nmax+5];
int nr = 0;
vector<vector<int>> comp;
void dfs(int node) {
idx[node] = timer; lowlink[node] = timer;
timer++;
st.emplace(node); onstack[node] = true;
for(auto next : dx[node]) {
if(idx[next] == -1)
dfs(next);
if(onstack[next])
lowlink[node] = min(lowlink[node], lowlink[next]);
}
if(idx[node] == lowlink[node]) {
nr++;
int curr;
vector<int> temp;
do {
curr = st.top(); st.pop();
onstack[curr] = false;
temp.emplace_back(curr);
} while(curr != node);
comp.emplace_back(temp);
}
}
int main() {
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m; f >> n >> m;
for(int i=1; i<=m; i++) {
int x, y; f >> x >> y;
dx[x].emplace_back(y);
}
for(int i=1; i<=n; i++) idx[i] = -1;
for(int i=1; i<=n; i++) if(idx[i] == -1) dfs(i);
g << nr << "\n";
for(int i=0; i<nr; i++, g << "\n")
for(auto x : comp[i])
g << x << " ";
return 0;
}