Pagini recente » Cod sursa (job #1758863) | Cod sursa (job #1936996) | Cod sursa (job #696959) | Cod sursa (job #2542095) | Cod sursa (job #591068)
Cod sursa(job #591068)
#include <iostream>
#include <fstream>
#include <stack>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
vector<vector<int> > g;
int n;
char *id, *idl;
int d = 0;
stack<int> s;
char *in_s;
ostringstream ss("");
int numar = 0;
void tarjan(int u) {
id[u] = idl[u] = d++;
s.push(u);
in_s[u] = 1;
int c;
for (unsigned int i = 0; i < g[u].size(); i++) {
c = g[u][i];
if (id[c] == -1) {
tarjan(c);
if (idl[u] > idl[c]) {
idl[u] = idl[c];
}
} else if (in_s[c] == 1) {
if (idl[u] > id[c]) {
idl[u] = id[c];
}
}
}
if (id[u] == idl[u]) {
numar++;
int v;
do {
v = s.top();
s.pop();
in_s[v] = 0;
ss << (int) v + 1 << " ";
}
while (v != u);
ss << endl;
}
}
int main() {
ifstream in("ctc.in", ifstream::in);
in >> n;
id = new char[n];
idl = new char[n];
in_s = new char[n];
for (int i = 0; i < n; i++) {
id[i] = -1;
idl[i] = -1;
in_s[i] = 0;
g.push_back(*(new vector<int>()));
}
int m;
in >> m;
int u, v;
for (int i = 0; i < m; i++) {
in >> u;
in >> v;
g[u - 1].push_back(v - 1);
}
for (int i = 0; i < n; i++) {
if (id[i] == -1) {
tarjan(i);
}
}
delete [] id;
delete [] idl;
delete [] in_s;
in.close();
ofstream out("ctc.out", ofstream::out);
out << numar << endl << ss.str();
out.flush();
out.close();
}