Pagini recente » Cod sursa (job #1589758) | Cod sursa (job #3039973) | Cod sursa (job #2475334) | Cod sursa (job #156341) | Cod sursa (job #2498101)
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector< int > g[100005];
int index[100005], lowlink[100005], onst[100005];
int ind;
stack< int > st;
vector< int > ctc[100005];
int cnt = 0;
void strongconnect(int v) {
index[v] = ind;
lowlink[v] = ind;
ind++;
st.push(v);
onst[v] = 1;
for(int i = 0; i < g[v].size(); i++) {
int w = g[v][i];
if(index[w] == -1) {
strongconnect(w);
lowlink[v] = min(lowlink[v], lowlink[w]);
}
else if(onst[w] == 1) {
lowlink[v] = min(lowlink[v], index[w]);
}
}
if(lowlink[v] == index[v]) {
while(st.top() != v) {
ctc[cnt].push_back(st.top());
onst[st.top()] = 0;
st.pop();
}
ctc[cnt].push_back(v);
onst[v] = 0;
st.pop();
cnt++;
}
}
int main()
{
int n, m, x, y; in >> n >> m;
for(int i = 0; i < m; i++) {
in >> x >> y;
g[x].push_back(y);
}
for(int i = 0; i <= n; i++){
index[i] = -1;
}
ind = 0;
for(int i = 1; i <= n; i++) {
if(index[i] == -1)
strongconnect(i);
}
out << cnt << endl;
for(int i = 0; i < cnt; i++) {
for(int j = 0; j < ctc[i].size(); j++) {
out << ctc[i][j] << " ";
}
out << endl;
}
return 0;
}