yeputons

Untitled

Jul 11th, 2012
201
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <cassert>
  6. #include <algorithm>
  7. #include <string>
  8. #include <vector>
  9. #include <deque>
  10. #include <queue>
  11. #include <map>
  12. #include <set>
  13.  
  14. using namespace std;
  15.  
  16. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  17. #define pb push_back
  18. #define mp make_pair
  19. #define sz(x) ((int)(x).size())
  20.  
  21. typedef long long ll;
  22. typedef vector<ll> vll;
  23. typedef vector<int> vi;
  24. typedef vector<vi> vvi;
  25. typedef vector<bool> vb;
  26. typedef vector<vb> vvb;
  27. typedef pair<int, int> pii;
  28.  
  29. const int MAXN = 1e5 + 1e3;
  30. const int MAXM = 5e5 + 1e3;
  31.  
  32. struct Edge { int to, ne; } es[MAXM], rves[MAXM];
  33. int ecnt;
  34. int firs[MAXN];
  35. int rfirs[MAXN];
  36.  
  37. bool was[MAXN];
  38.  
  39. int ord[MAXN];
  40. int oend;
  41.  
  42. void dfs(int v) {
  43.   if (was[v]) return;
  44.   was[v] = true;
  45.   for (int i = firs[v]; i >= 0; i = es[i].ne)
  46.     dfs(es[i].to);
  47.   ord[oend++] = v;
  48. }
  49.  
  50. int cols[MAXN];
  51. int ccol;
  52. int colsz[MAXN];
  53. int collast[MAXN];
  54.  
  55. void dfs2(int v) {
  56.   if (was[v]) return;
  57.   was[v] = true;
  58.   cols[v] = ccol; collast[ccol] = v;
  59.   colsz[ccol]++;
  60.   for (int i = rfirs[v]; i >= 0; i = rves[i].ne)
  61.     dfs2(rves[i].to);
  62. }
  63.  
  64. Edge tes[MAXN];
  65. pii tes2[MAXN];
  66. int tfirs[MAXN];
  67. int tecnt;
  68.  
  69. int colsubsz[MAXN];
  70. pii colpath[MAXN];
  71.  
  72. void dfs3(int v) {
  73.   colsubsz[v] = colsz[v];
  74.   colpath[v] = mp(0, -1);
  75.   for (int i = tfirs[v]; i >= 0; i = tes[i].ne) {
  76.     int b = tes[i].to;
  77.     dfs3(b);
  78.     colpath[v] = max(colpath[v], mp(1 + colpath[b].first, b));
  79.     colsubsz[v] += colsubsz[b];
  80.   }
  81. }
  82.  
  83. pii ans[MAXN];
  84. int alen;
  85.  
  86. void dfs4(int v, int locroot) {
  87.   was[v] = true;
  88.   int deg = 0;
  89.   for (int i = firs[v]; i >= 0; i = es[i].ne) {
  90.     int b = es[i].to;
  91.     if (cols[b] == cols[v]) continue;
  92.     if (was[b]) continue;
  93.  
  94.     dfs4(b, deg == 0 ? locroot : v);
  95.     deg++;
  96.   }
  97.   if (v != locroot && deg == 0)
  98.     ans[alen++] = mp(v, locroot);
  99. }
  100.  
  101. int main() {
  102.   #ifdef DEBUG
  103.   freopen("std.in", "r", stdin);
  104.   freopen("std.out", "w", stdout);
  105.   #endif
  106.  
  107.   int n, m, root;
  108.   while (scanf("%d%d%d", &n, &m, &root) >= 1) {
  109.     root--;
  110.     memset(firs, -1, sizeof(firs[0]) * n);
  111.     memset(rfirs, -1, sizeof(rfirs[0]) * n);
  112.     ecnt = 0;
  113.  
  114.     for (int i = 0; i < m; i++) {
  115.       int a, b;
  116.       scanf("%d%d", &a, &b), a--, b--;
  117.  
  118.       es[ecnt].to = b;
  119.       es[ecnt].ne = firs[a];
  120.       firs[a] = ecnt;
  121.  
  122.       rves[ecnt].to = a;
  123.       rves[ecnt].ne = rfirs[b];
  124.       rfirs[b] = ecnt;
  125.  
  126.       ecnt++;
  127.     }
  128.  
  129.     oend = 0;
  130.     memset(was, 0, sizeof(was[0]) * n);
  131.     dfs(root);
  132.     assert(oend == n);
  133.  
  134.     memset(was, 0, sizeof(was[0]) * n);
  135.     memset(cols, -1, sizeof(cols[0]) * n);
  136.     ccol = 0;
  137.     for (int i = oend - 1; i >= 0; i--) {
  138.       int v = ord[i];
  139.       if (was[v]) continue;
  140.  
  141.       colsz[ccol] = 0;
  142.       dfs2(v);
  143.       ccol++;
  144.     }
  145.     int rcol = cols[root];
  146.  
  147.     memset(tfirs, -1, sizeof(tfirs[0]) * ccol);
  148.     tecnt = 0;
  149.     for (int a = 0; a < n; a++)
  150.     for (int i = firs[a]; i >= 0; i = es[i].ne) {
  151.       int b = es[i].to;
  152.       if (cols[a] == cols[b]) continue;
  153.  
  154.       assert(tecnt < ccol - 1);
  155.       tes[tecnt].to = cols[b];
  156.       tes[tecnt].ne = tfirs[cols[a]];
  157.       tes2[tecnt] = mp(a, b);
  158.       tfirs[cols[a]] = tecnt++;
  159.     }
  160.     assert(tecnt == ccol - 1);
  161.  
  162.     dfs3(rcol);
  163.     for (int i = 0; i < n; i++)
  164.       printf("%d%c", colsubsz[cols[i]], "\n "[i + 1 < n]);
  165.  
  166.     alen = 0;
  167.     memset(was, 0, sizeof(was[0]) * n);
  168.     for (int i = n - 1; i >= 0; i--) {
  169.       int v = ord[i];
  170.       if (!was[v])
  171.         dfs4(v, v);
  172.     }
  173.  
  174.     printf("%d\n", alen);
  175.     for (int i = 0; i < alen; i++)
  176.       printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
  177.   }
  178.   return 0;
  179. }
RAW Paste Data