LOJ10092半连通子图

2024-09-08 05:25:51

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

Sample Output

3

3

——————————————————————————————————————————————

题目大意：

一个有向图，求图中的最大半连通子图的点数和方案数。

首先，对图进行缩点。因为环内的点肯定是连通的。

然后，图就变成了有向无环图，这样在上面进行拓扑排序。

最后，在拓扑序上进行DP。

只得了40分，后来看别的程序才发现问题，注意去重边。

——————————————————————————————————————————————

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int maxn=1e5+10,maxm=1e6+10;

 4 struct edge

 5 {

 6     int u,v,nxt;

 7 }e[maxm],ee[maxm];

 8 int head[maxn],js,headd[maxn],jss;

 9 void addage(edge e[],int head[],int &js,int u,int v)

10 {

11     e[++js].u=u;e[js].v=v;

12     e[js].nxt=head[u];head[u]=js;

13 }

14 int dfn[maxn],low[maxn],cnt,st[maxn],top,lt[maxn],lts,ltn[maxn];

15 void  tarjan(int u)

16 {

17     dfn[u]=low[u]=++cnt;

18     st[++top]=u;

19     for(int i=head[u];i;i=e[i].nxt)

20     {

21         int v=e[i].v;

22         if(!dfn[v])

23         {

24             tarjan(v);

25             low[u]=min(low[u],low[v]);

26         }

27         else if(!lt[v])

28             low[u]=min(low[u],dfn[v]);

29     }

30     if(dfn[u]==low[u])

31     {

32         lt[u]=++lts;ltn[lts]++;

33         while(st[top]!=u)lt[st[top--]]=lts,ltn[lts]++;

34         --top;

35     }

36 }

37 int n,m,x;

38 int f[maxn],ff[maxn];

39 int cd[maxn],rd[maxn];

40 int maxd,maxf;

41 int pc[maxn];

42 queue<int>q;

43 void dfs()

44 {

45     while(!q.empty())

46     {

47         int u=q.front();q.pop();

48         maxd=max(maxd,f[u]);

49         for(int i=headd[u];i;i=ee[i].nxt)

50         {

51             int v=ee[i].v;

52             rd[v]--;

53             if(rd[v]==0)q.push(v);

54             if(pc[v]==u)continue;

55             if(f[u]+ltn[v]>f[v])

56             {

57                 f[v]=f[u]+ltn[v];

58                 ff[v]=ff[u];

59

60             }

61             else if(f[u]+ltn[v]==f[v])

62             {

63                 ff[v]=(ff[u]+ff[v])%x;

64             }

65             pc[v]=u;

66         }

67     }

68 }

69 int main()

70 {

71     scanf("%d%d%d",&n,&m,&x);

72     for(int u,v,i=1;i<=m;++i)

73     {

74         scanf("%d%d",&u,&v);

75         addage(e,head,js,u,v);

76     }

77     for(int i=1;i<=n;++i)

78         if(!dfn[i])tarjan(i);

79     for(int u=1;u<=n;++u)

80         for(int i=head[u];i;i=e[i].nxt)

81             if(lt[e[i].u]!=lt[e[i].v])addage(ee,headd,jss,lt[e[i].u],lt[e[i].v]),cd[lt[e[i].u]]++,rd[lt[e[i].v]]++;

82     for(int i=1;i<=lts;++i)

83         if(rd[i]==0)q.push(i),f[i]=ltn[i],ff[i]=1;

84     dfs();

85     for(int i=1;i<=lts;++i)

86     {

87         if(f[i]==maxd)maxf=(maxf+ff[i])%x;

88     }

89     printf("%d\n%d\n",maxd,maxf);

90     return 0;

91 }

最新文章

热门文章