Pagini recente » Cod sursa (job #2203210) | Cod sursa (job #466342) | Cod sursa (job #1086394) | Cod sursa (job #1262750) | Cod sursa (job #445987)
Cod sursa(job #445987)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <list>
using namespace std;
#define FILEIN "ctc.in"
#define FILEOUT "ctc.out"
#define NMAX 100001
#define MMAX 200001
int G[MMAX];
int pos[NMAX];
int n, m;
int T = 0;
int td[NMAX];
int low[NMAX];
bool onstack[NMAX];
list<list<int>* >ctcs;
void read_data() {
ifstream fin;
fin.open(FILEIN);
fin >> n >> m;
for (int i = 0; i < n; i++) {
pos[i] = 0;
}
for (int i = 0; i < m; i++) {
int u, v;
fin >> u >> v;
pos[u - 1]++;
}
for (int i = 1; i < n; i++) {
pos[i] += pos[i - 1];
}
pos[n] = pos[n - 1];
// take a second walk through input data
fin.seekg(0, ios::beg);
fin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
fin >> u >> v;
pos[u - 1]--;
G[pos[u - 1]] = v - 1;
}
fin.close();
}
void print_graph() {
for (int u = 0; u < n; u++) {
cout << u << ": ";
for (int i = pos[u]; i < pos[u + 1]; i++) {
int v = G[i];
cout << v << " -> ";
}
cout << endl;
}
}
void print_ctc(ofstream &f, list<int> *ctc) {
list<int>::const_iterator it;
for (it = ctc->begin(); it != ctc->end(); it++) {
int u = *it + 1;
f << u << " ";
}
f << endl;
}
void print_results() {
ofstream fout;
fout.open(FILEOUT);
fout << ctcs.size() << endl;
list<list<int>* >::const_iterator it;
for (it = ctcs.begin(); it != ctcs.end(); it++) {
print_ctc(fout, *it);
}
fout.close();
}
void add_ctc(list<int> *ctc) {
ctcs.push_back(ctc);
}
void dfs_tarjan(int u, stack<int> &s) {
td[u] = T;
low[u] = T;
T++;
s.push(u);
onstack[u] = true;
for (int i = pos[u]; i < pos[u + 1]; i++) {
int v = G[i];
if (td[v] < 0) {
dfs_tarjan(v, s);
}
if (onstack[v]) {
if (low[v] < low[u])
low[u] = low[v];
}
}
if (low[u] == td[u]) {
// is root
list<int> *ctc = new list<int>();
while (!s.empty()) {
int v = s.top();
ctc->push_back(v);
onstack[v] = false;
s.pop();
if (v == u)
break;
}
add_ctc(ctc);
}
}
int main(void) {
read_data();
stack<int> s;
// init
for (int i = 0; i < n; i++) {
low[i] = -1;
td[i] = -1;
onstack[i] = false;
}
for (int i = 0; i < n; i++) {
if (td[i] < 0)
dfs_tarjan(i, s);
}
print_results();
}