Pagini recente » Cod sursa (job #1847772) | Cod sursa (job #3137715) | Cod sursa (job #1147777) | Cod sursa (job #1844065) | Cod sursa (job #445990)
Cod sursa(job #445990)
#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
#define END -1
int G[MMAX];
int pos[NMAX];
int n, m;
int T = 0;
int td[NMAX];
int low[NMAX];
bool onstack[NMAX];
int ctc_no = 0;
int ictc = 0;
int ctcs[2 * NMAX];
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_results() {
ofstream fout;
fout.open(FILEOUT);
fout << ctc_no << endl;
for (int i = 0, ic = 0; i < ctc_no; ic++) {
if (ctcs[ic] != END) {
fout << ctcs[ic] + 1 << " ";
} else {
i++;
fout << endl;
}
}
fout.close();
}
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
ctc_no++;
while (!s.empty()) {
int v = s.top();
ctcs[ictc] = v;
ictc++;
onstack[v] = false;
s.pop();
if (v == u)
break;
}
ctcs[ictc] = END;
ictc++;
}
}
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();
}