BZOJ1064【NOI2008】假面舞会 <连通分量>

Posted on Symbols count in article: 1.2k Reading time ≈ 4 mins.

Problem

【NOI2008】假面舞会

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  162  MB\mathrm{Memory\;Limit:\;162\;MB}

Description

一年一度的假面舞会又开始了，栋栋也兴致勃勃的参加了今年的舞会。
今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一 个自己喜欢的面具。
每个面具都有一个编号，主办方会把此编号告诉拿该面具的人。为了使舞会更有神秘感，主办方把面具分为k  (k≥3)k\;(k\ge3)类，并使用特殊的技术将每个面具的编号标在了面具上，只有戴第ii类面具的人才能看到戴第i+1i+1类面具的人的编号，戴第kk类面具的人能看到戴第11类面具的人的编号。
参加舞会的人并不知道有多少类面具，但是栋栋对此却特别好奇，他想自己算出有多少类面具，于是他开始在人群中收集信息。 栋栋收集的信息都是戴第几号面具的人看到了第几号面具的编号。如戴第22号面具的人看到了第55号面具的编号。栋栋自己也会看到一些编号，他也会根据自己的面具编号把信息补充进去。由于并不是每个人都能记住自己所看到的全部编号，因此，栋栋收集的信 息不能保证其完整性。现在请你计算，按照栋栋目前得到的信息，至多和至少有多少类面具。由于主办方已经声明了k≥3k\ge3，所以你必须将这条信息也考虑进去。

Input

第一行包含两个整数n,mn,m，用一个空格分隔，nn表示主办方总共准备了多少个面具，mm表示栋栋收集了多少条信息。
接下来mm行，每行为两个用空格分开的整数a,ba,b，表示戴第aa号面具的人看到了第bb号面具的编号。相同的数对a,ba,b在输入文件中可能出现多次。

Output

包含两个数，第一个数为最大可能的面具类数，第二个数为最小可能的面具类数。
如果无法将所有的面具分为至少33类，使得这些信息都满足，则认为栋栋收集的信息有错误，输出两个−1-1。

Sample

Sample Input 1

1
2
3
4
5
6
6 5
1 2
2 3
3 4
4 1
3 5

Sample Output 1

1
4 4

Sample Input 2

1
2
3
4
3 3
1 2
2 1
2 3

Sample Output 2

1
-1 -1

HINT

100%100\%的数据，满足n≤105,m≤106n\le10^5,m\le10^6。

标签：连通分量

Solution

图论好题，比较常规的连通分量做法，不过有几个细节容易出错。

对于给定的有向图，只会有两种情况：

  • 存在环：所有环长度的最大公约数gcd\mathrm{gcd}为最大类数，大于33且整除gcd\mathrm{gcd}的最小数为最小类数。
  • 不存在环：所有连通块的最长链之和为最大类数，33为最小类数。

特判一下最大类数是否大于等于33即可判断是否无解。

注意这里直接跑tarjan是无法找出所有环长的，需要DFS\mathrm{DFS}直接找。
对每条边建长为−1-1的反边，即可跑DFS\mathrm{DFS}找出环长和最长链，分情况讨论即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define MAX_N 100000
#define MAX_M 1000000
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, mi, mx, mid, mxd, cnt, pr[MAX_N+5], d[MAX_N+5];
struct edge {int v, c, nxt;} E[MAX_M<<1]; bool mrk[MAX_N+5], vis[MAX_M<<1];
int gcd(int a, int b) {return b ? gcd(b, a%b) : a;}
void insert(int u, int v, int c) {E[cnt] = (edge){v, c, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v) {insert(u, v, 1), insert(v, u, -1);}
void DFS(int u) {
    mrk[u] = true;
    for (int i = pr[u], v; ~i; i = E[i].nxt)
        if (!mrk[v = E[i].v]) d[v] = d[u]+E[i].c, DFS(v);
        else mx = gcd(mx, abs(d[u]-d[v]+E[i].c));
}
void getD(int u) {
    mrk[u] = true, mxd = max(mxd, d[u]), mid = min(mid, d[u]);
    for (int i = pr[u]; ~i; i = E[i].nxt) if (!vis[i])
        vis[i] = vis[i^1] = true, d[E[i].v] = d[u]+E[i].c, getD(E[i].v);
}
int main() {
    read(n), read(m), memset(pr, -1, sizeof pr);
    for (int i = 1, u, v; i <= m; i++)
        read(u), read(v), addedge(u, v);
    for (int i = 1; i <= n; i++) if (!mrk[i]) DFS(i);
    if (mx) {
        if (mx < 3) {puts("-1 -1"); return 0;}
        for (mi = 3; mi <= mx; mi++) if (!(mx%mi)) break;
    } else {
        memset(mrk, false, sizeof mrk), mi = 3;
        for (int i = 1; i <= n; i++) if (!mrk[i])
            mxd = mid = d[i] = 0, getD(i), mx += mxd-mid+1;
        if (mx < 3) {puts("-1 -1"); return 0;}
    }
    return printf("%d %d\n", mx, mi), 0;
}