1093: [ZJOI2007]最大半连通子图
Description
一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：?u,v∈V，满足u→v或v→u，即对于图中任意
两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。若G'=(V',E')满足V'?V，E'是E中所有跟V'有关的边，
则称G'是G的一个导出子图。若G'是G的导出子图，且G'半连通，则称G'为G的半连通子图。若G'是G所有半连通子图
中包含节点数最多的，则称G'是G的最大半连通子图。给定一个有向图G，请求出G的最大半连通子图拥有的节点数K
，以及不同的最大半连通子图的数目C。由于C可能比较大，仅要求输出C对X的余数。
Input
第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述接下来M行，每行两个正整
数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。N ≤1
00000, M ≤1000000；对于100%的数据， X ≤10^8
Output
应包含两行，第一行包含一个整数K。第二行包含整数C Mod X.
Sample Input
6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4
1 2
2 1
1 3
2 4
5 6
6 4
Sample Output
3
3
3
HINT
Source
第一遍做时 思路还是比较正确
先tarjan缩点 再建新图 从入度为0的点跑 bfs 求最长链及条数
但是只有30分 因为我建完新图没有判重边 还有不知名的MLE和TLE (我也很绝望啊)
后来才知道 这个新图内不能有重边
于是就 判重之后就拓扑排序 统计在这个点的半连通子图的点数和个数
1 #include <queue>
2 #include <cstdio>
3 #include <cctype>
4
5 const int MAXN=100010;
6
7 int n,m,mod,id,inr,top,ans,total;
8
9 int dfn[MAXN],low[MAXN],stack[MAXN],belong[MAXN],siz[MAXN],in[MAXN];
10
11 int f[MAXN][2];
12
13 bool vis[MAXN];
14
15 struct node {
16 int to;
17 int next;
18 node() {}
19 node(int to,int next):to(to),next(next) {}
20 };
21 node e[MAXN*10],r[MAXN*10];
22
23 int head[MAXN],tot,Head[MAXN],tal;
24
25 inline void read(int&x) {
26 int f=1;register char c=getchar();
27 for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar());
28 for(;isdigit(c);x=x*10+c-48,c=getchar());
29 x=x*f;
30 }
31
32 inline void add(int x,int y) {
33 e[++tot]=node(y,head[x]);
34 head[x]=tot;
35 }
36
37 inline int min(int a,int b) {return a<b?a:b;}
38
39 inline bool pd(int u,int v) {
40 for(int i=Head[u];i;i=r[i].next)
41 if(r[i].to==v) return true;
42 return false;
43 }
44
45 void tarjan(int u) {
46 dfn[u]=low[u]=++inr;
47 stack[++top]=u;
48 vis[u]=true;
49 for(int i=head[u];i;i=e[i].next) {
50 int v=e[i].to;
51 if(!dfn[v]) {
52 tarjan(v);
53 low[u]=min(low[u],low[v]);
54 }
55 else if(vis[v]) low[u]=min(low[u],dfn[v]);
56 }
57 if(dfn[u]==low[u]) {
58 ++id;
59 int t;
60 do {
61 ++siz[id];
62 t=stack[top--];
63 vis[t]=false;
64 belong[t]=id;
65 vis[t]=false;
66 }while(u!=t);
67 }
68 }
69
70 int hh() {
71 read(n);read(m);read(mod);
72 for(int x,y,i=1;i<=m;++i) {
73 read(x);read(y);
74 add(x,y);
75 }
76 for(int i=1;i<=n;++i)
77 if(!dfn[i]) tarjan(i);
78 for(int i=1;i<=n;++i)
79 for(int j=head[i];j;j=e[j].next) {
80 int v=e[j].to;
81 if(belong[i]!=belong[v]) {
82 if(pd(belong[i],belong[v])) continue;
83 ++in[belong[v]];
84 r[++tal]=node(belong[v],Head[belong[i]]);
85 Head[belong[i]]=tal;
86 }
87 }
88 std::queue<int> q;
89 for(int i=1;i<=id;++i) {
90 f[i][0]=siz[i];f[i][1]=1;
91 if(!in[i]) q.push(i);
92 }
93 while(!q.empty()) {
94 int u=q.front();;
95 q.pop();
96 for(int i=Head[u];i;i=r[i].next) {
97 int v=r[i].to;
98 --in[v];
99 if(!in[v]) q.push(v);
100 if(f[v][0]<f[u][0]+siz[v]) f[v][0]=f[u][0]+siz[v],f[v][1]=f[u][1];
101 else if(f[v][0]==f[u][0]+siz[v]) f[v][1]+=f[u][1],f[v][1]%=mod;
102 }
103 }
104 for(int i=1;i<=id;++i) {
105 if(f[i][0]>ans) ans=f[i][0],total=f[i][1];
106 else if(f[i][0]==ans) total+=f[i][1],total%=mod;
107 }
108 printf("%d
%d
",ans,total);
109 return 0;
110 }
111
112 int sb=hh();
113 int main (int argc,char**argv) {;}