首页 > 代码库 > 最大半连通子图 bzoj 1093
最大半连通子图 bzoj 1093
最大半连通子图 (1.5s 128MB) semi
【问题描述】
一个有向图G = (V,E)称为半连通的(Semi-Connected)，如果满足：? u, v ∈V，满足u—>v 或 v —> u，即对于图中任意两点u,v, 存在一条u到v的有向路径或者从v到u的有向路径。
若满足，则称G’是G的一个导出子图。
若G’是G的导出子图，且G’半连通，则称G’为G的半连通子图。
若G’是G所有半连通子图中包含节点数最多的，则称G’是G的最大半连通子图。
给定一个有向图G，请求出G的最大半连通子图拥有的节点数K，以及不同的最大半连通子图的数目C。由于C可能比较大，仅要求输出C对X的余数。
【输入文件】
第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述。接下来M行，每行两个正整数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。
【输出文件】
应包含两行，第一行包含一个整数K。第二行包含整数C Mod X.
【样例输入】
6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4
【样例输出】
3
3
【数据规模】
对于20%的数据， N ≤ 18；
对于60%的数据， N ≤ 10000；
对于100%的数据， N ≤ 100000, M ≤ 1000000；
对于100%的数据， X ≤ 108。
题解：
主要算法：强连通分量；拓扑排序；递推；
首先用Tarjon缩点，去重连边，得到新图，那么题目就变成了求图中最长链及最长链个数
最长链可以直接用拓扑排序
最长链个数用一个类似递推的方法
记录每一个点的方案数
那么当前点的方案数就等于连到此点且满足距离相等的点的方案数之和
最后查找距离等于最长链的点，答案为它们的方案数之和
1 #include<algorithm>
2 #include<iostream>
3 #include<cstdlib>
4 #include<cstring>
5 #include<cstdio>
6 #include<cmath>
7 using namespace std;
8 inline int Get()
9 {
10 int x = 0;
11 char c = getchar();
12 while(‘0‘ > c || c > ‘9‘) c = getchar();
13 while(‘0‘ <= c && c <= ‘9‘)
14 {
15 x = (x << 3) + (x << 1) + c - ‘0‘;
16 c = getchar();
17 }
18 return x;
19 }
20 const int me = 1000233;
21 int n, m, mo;
22 int x[me], y[me];
23 int tot;
24 int de[me], to[me], fir[me], nex[me];
25 int ue[me];
26 int si[me];
27 inline void Ins(int x, int y)
28 {
29 nex[++tot] = fir[x];
30 fir[x] = tot;
31 to[tot] = y;
32 }
33 int num, top, col;
34 int ti[me], lo[me], st[me], co[me];
35 inline void Tarjan(int u)
36 {
37 ti[u] = lo[u] = ++num;
38 st[++top] = u;
39 for(int i = fir[u]; i; i = nex[i])
40 {
41 int v = to[i];
42 if(!ti[v])
43 {
44 Tarjan(v);
45 lo[u] = min(lo[u], lo[v]);
46 }
47 else
48 if(!co[v])
49 lo[u] = min(lo[u], ti[v]);
50 }
51 if(lo[u] == ti[u])
52 {
53 co[u] = ++col;
54 ++si[col];
55 while(st[top] != u)
56 {
57 ++si[col];
58 co[st[top]] = col;
59 --top;
60 }
61 --top;
62 }
63 }
64 int t, w;
65 int ans;
66 int e[me];
67 int dis[me];
68 inline bool rule(int a, int b)
69 {
70 if(x[a] != x[b]) return x[a] < x[b];
71 return y[a] < y[b];
72 }
73 int nu[me];
74 inline void Remove()
75 {
76 for(int i = 1; i <= m; ++i)
77 {
78 nu[i] = i;
79 x[i] = co[x[i]];
80 y[i] = co[y[i]];
81 }
82 sort(nu + 1, nu + 1 + m, rule);
83 }
84 inline void Build()
85 {
86 tot = 0;
87 memset(fir, 0, sizeof(fir));
88 for(int i = 1; i <= m; ++i)
89 {
90 int z = nu[i];
91 if((x[z] != y[z]) && (x[z] != x[nu[i - 1]] || y[z] != y[nu[i - 1]]))
92 {
93 ++de[y[z]];
94 Ins(x[z], y[z]);
95 }
96 }
97 }
98 inline void Reset()
99 {
100 for(int i = 1; i <= col; ++i)
101 if(!de[i])
102 {
103 ue[++w] = i;
104 dis[i] = si[i];
105 e[i] = 1;
106 if(dis[ans] < dis[i]) ans = i;
107 }
108 }
109 inline void Topo()
110 {
111 while(t < w)
112 {
113 int u = ue[++t];
114 for(int i = fir[u]; i; i = nex[i])
115 {
116 int v = to[i];
117 --de[v];
118 if(dis[v] < dis[u] + si[v])
119 {
120 dis[v] = dis[u] + si[v];
121 e[v] = 0;
122 if(dis[ans] < dis[v]) ans = v;
123 }
124 if(dis[v] == dis[u] + si[v])
125 e[v] = (e[v] + e[u]) % mo;
126 if(!de[v]) ue[++w] = v;
127 }
128 }
129 }
130 int anss;
131 inline void Ask()
132 {
133 for(int i = 1; i <= n; ++i)
134 if(dis[i] == dis[ans])
135 anss = (anss + e[i]) % mo;
136 }
137 int main()
138 {
139 n = Get(), m = Get(), mo = Get();
140 for(int i = 1; i <= m; ++i)
141 {
142 x[i] = Get(), y[i] = Get();
143 Ins(x[i], y[i]);
144 }
145 for(int i = 1; i <= n; ++i)
146 if(!ti[i])
147 Tarjan(i);
148 Remove();
149 Build();
150 Reset();
151 Topo();
152 Ask();
153 printf("%d\n%d", dis[ans], anss);
154 }
最大半连通子图 bzoj 1093