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