Pagini recente » Cod sursa (job #1946535) | Istoria paginii runda/concurs_9_17/clasament | Cod sursa (job #1410254) | Cod sursa (job #633709) | Cod sursa (job #2081612)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
const int NMAX = 100000 + 1;
int n;
int ind;
bool in_stack[NMAX];
int index_nod[NMAX];
int lowlink[NMAX];
vector <int> graf[NMAX];
stack <int> st;
vector < vector <int> > sol;
void citeste() {
int m, a, b;
f >> n >> m;
while (m--) {
f >> a >> b;
graf[a].push_back(b);
}
}
int ctc(int nod) {
if (index_nod[nod]) return index_nod[nod];
index_nod[nod] = ++ind;
lowlink[nod] = ind;
st.push(nod);
in_stack[nod] = true;
int lowlink_crt = ind;
int l = graf[nod].size();
for (int i = 0; i < l; i++) {
int fiu = graf[nod][i];
int lowlink_fiu = ctc(fiu);
if (!in_stack[fiu]) continue;
lowlink_crt = min(lowlink_crt, lowlink_fiu);
}
lowlink[nod] = lowlink_crt;
if (lowlink[nod] != index_nod[nod]) return lowlink[nod];
vector <int> comp_crt;
int top;
do {
top = st.top();
st.pop();
in_stack[top] = false;
comp_crt.push_back(top);
} while(top != nod);
sol.push_back(comp_crt);
return lowlink[nod];
}
void rezolva() {
for (int i = 1; i <= n; i++)
if (!index_nod[i]) ctc(i);
}
void scrie() {
int l = sol.size();
g << l << '\n';
for (int i = 0; i < l; i++) {
int k = sol[i].size();
for (int j = 0; j < k; j++) {
g << sol[i][j] << ' ';
}
g << '\n';
}
}
int main() {
citeste();
rezolva();
scrie();
return 0;
}