Pagini recente » Cod sursa (job #500747) | Cod sursa (job #791793) | Cod sursa (job #2725043) | Cod sursa (job #960753) | Cod sursa (job #446011)
Cod sursa(job #446011)
#include <string.h>
#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
#define WHITE 0
#define GRAY 1
#define BLACK 2
int G[MMAX];
int G_t[MMAX];
int pos[NMAX];
int pos_t[NMAX];
int n, m;
int color[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;
pos_t[i] = 0;
}
for (int i = 0; i < m; i++) {
int u, v;
fin >> u >> v;
pos[u - 1]++;
pos_t[v - 1]++;
}
for (int i = 1; i < n; i++) {
pos[i] += pos[i - 1];
pos_t[i] += pos_t[i - 1];
}
pos[n] = pos[n - 1];
pos_t[n] = pos_t[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;
u--; v--;
pos[u]--;
G[pos[u]] = v;
pos_t[v]--;
G_t[pos_t[v]] = u;
}
fin.close();
}
void print_graph(int pos[NMAX], int G[MMAX]) {
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 first_dfs(int u, stack<int> &s) {
color[u] = GRAY;
for (int i = pos[u]; i < pos[u + 1]; i++) {
int v = G[i];
if (color[v] == WHITE) {
first_dfs(v, s);
}
}
s.push(u);
color[u] = BLACK;
}
void dfs_t(int u) {
color[u] = GRAY;
for (int i = pos_t[u]; i < pos_t[u + 1]; i++) {
int v = G_t[i];
if (color[v] == WHITE) {
dfs_t(v);
}
}
ctcs[ictc] = u;
ictc++;
color[u] = BLACK;
}
int main(void) {
read_data();
stack<int> s;
memset(color, WHITE, sizeof(color));
for (int u = 0; u < n; u++) {
if (color[u] == WHITE) {
first_dfs(u, s);
}
}
memset(color, WHITE, sizeof(color));
while (!s.empty()) {
int u = s.top();
if (color[u] == WHITE) {
ctc_no++;
dfs_t(u);
// add marker
ctcs[ictc] = END;
ictc++;
}
s.pop();
}
print_results();
}