Pagini recente » Cod sursa (job #1876830) | Cod sursa (job #970344) | Cod sursa (job #2634509) | Cod sursa (job #174197) | Cod sursa (job #2924870)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define dim 100002
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, a, b, cnt = 0, id = 0;
vector< vector<int> > lists(dim);
vector<bool> onStack(dim);
vector<int> low(dim), disc(dim);
stack<int> stk;
void tarjan(int nod) {
stk.push(nod);
onStack[nod] = true;
disc[nod] = low[nod] = ++id;
for (int i = 0; i < lists[nod].size(); i++) {
int vecin = lists[nod][i];
if (disc[vecin] == 0) {
tarjan(vecin);
}
if( onStack[vecin] ) {
low[nod] = min(low[nod], low[vecin]);
}
}
if (disc[nod] == low[nod]) {
while (stk.top() != nod) {
onStack[stk.top()] = false;
low[stk.top()] = disc[nod];
stk.pop();
}
onStack[stk.top()] = false;
low[stk.top()] = disc[nod];
stk.pop();
cnt++;
}
}
int main() {
fin >> n >> m;
for (int i = 0; i < m; i++) {
fin >> a >> b;
lists[a].push_back(b);
}
for (int i = 1; i <= n; i++) {
if (disc[i] == 0) {
tarjan(i);
}
}
fout << cnt << "\n" << 1;
for(int i = 2; i <= n; i++) {
if( low[i] == low[i - 1] )
fout << " " << i;
else fout << '\n' << i;
}
fout << '\n';
return 0;
}