Pagini recente » Cod sursa (job #1321342) | Cod sursa (job #183155) | Cod sursa (job #147699) | Cod sursa (job #396128) | Cod sursa (job #444410)
Cod sursa(job #444410)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <list>
using namespace std;
#define FILEIN "ctc.in"
#define FILEOUT "ctc.out"
#define NMAX 1000
list<int> G[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 < m; i++) {
int u, v;
fin >> u >> v;
G[u - 1].push_back(v - 1);
}
fin.close();
}
void print_graph() {
for (int u = 0; u < n; u++) {
cout << u << ": ";
list<int>::const_iterator it;
for (it = G[u].begin(); it != G[u].end(); it++) {
cout << *it << " -> ";
}
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;
list<int>::const_iterator it;
for (it = G[u].begin(); it != G[u].end(); it++) {
int v = *it;
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();
}