首页 > 代码库 > 图论算法----强连通

图论算法----强连通

2024-07-07 13:11:10   226人阅读

poj 2186 Popular Cows

分析：直接求一下强连通分量，对于同一个强连通分量里面的结点状态是相同的，要求有多少个人被其他所有的人都认可，只有可能是拓扑排序的最后一个强连通的结点个数，判断一下其他节点是否都可以到该联通分量就ok了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <set>
 5 #include <algorithm>
 6 #include <map>
 7 #include<vector>
 8 #define maxn 10010
 9 #define maxm 50010
10 using namespace std;
11 int n,m;
12 vector<int>G[maxn];
13 vector<int>rG[maxn];
14 vector<int>vs;
15 bool used[maxn];
16 int cmp[maxn];
17 void addedge(int u,int v){
18     G[u].push_back(v);
19     rG[v].push_back(u);
20 }
21 void init(){
22     for(int i=0;i<=n;++i){
23         G[i].clear();
24         rG[i].clear();
25     }
26 }
27 void dfs(int u){
28     used[u]=true;
29     for(int i=0;i<G[u].size();++i){
30         if(!used[G[u][i]])dfs(G[u][i]);
31     }
32     vs.push_back(u);
33 }
34 void rdfs(int u,int k){
35     used[u]=true;
36     cmp[u]=k;
37     for(int i=0;i<rG[u].size();++i){
38         if(!used[rG[u][i]])rdfs(rG[u][i],k);
39     }
40 }
41 int scc(){
42     memset(used,0,sizeof(used));
43     vs.clear();
44     for(int i=0;i<n;++i){
45         if(!used[i])dfs(i);
46     }
47     memset(used,0,sizeof(used));
48     int k =0;
49     for (int i=vs.size()-1;i>=0;--i){
50         if(!used[vs[i]])rdfs(vs[i],k++);
51     }
52     return k;
53 }
54 void solve(){
55     int nn = scc();
56     int cnt =0,u=0;
57     for(int i=0;i<n;++i){
58         if(cmp[i]==nn-1){
59             u = i;
60             cnt++;
61         }
62     }
63     memset(used,0,sizeof(used));
64     rdfs(u,0);
65     for(int i=0;i<n;++i){
66         if(!used[i]){
67             cnt=0;
68             break;
69         }
70     }
71     printf("%d\n",cnt);
72 }
73 int main (){
74     while(scanf("%d%d",&n,&m)!=EOF){
75         init();
76         int x,y;
77         for(int i=0;i<m;++i){
78             scanf("%d%d",&x,&y);
79             addedge(x-1,y-1);
80         }
81         solve();
82     }
83 }
View Code

poj3683   Priest John‘s Busiest Day

题目意思：有n个事务，每个有两种时间段选择，问你可不可以安排使得n个事务不冲突。

分析：转成2-SAT求解，对于每一个事务，有两种选择就是是或者否，根据相应的条件完成建图后使用强连通求解2-SAT

把第i个事务拆成两个点i i+m分别对应开始时间段与结束时间段，然后根据时间段是否有冲突写出合取范式建图求解

对于规则a∨b 可以改写为 ┐a->b∧┐b->a 可以翻一下离散的书

si与sj冲突那么就可以写成 ┐xi V ┐xj   转为xi->┐xj 建边(i,j+m)

同理另外三种情况看代码

利用强连通求解2-SAT只需要判断i结点与i+m结点是不是在一个强连通分支里面，如果在说明两者同时成立，这显然是不合理的。

如果i结点的拓扑序在i+m前面则i成立即第i个事务选择在开始时执行否则在结束时执行

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <set>
  5 #include <algorithm>
  6 #include <map>
  7 #include<vector>
  8 #define maxn 4010
  9 #define maxm 50010
 10 using namespace std;
 11 int n,m;
 12 vector<int>G[maxn];
 13 vector<int>rG[maxn];
 14 vector<int>vs;
 15 bool used[maxn];
 16 int cmp[maxn];
 17 void addedge(int u,int v){
 18     G[u].push_back(v);
 19     rG[v].push_back(u);
 20 }
 21 void init(){
 22     for(int i=0;i<=n;++i){
 23         G[i].clear();
 24         rG[i].clear();
 25     }
 26 }
 27 void dfs(int u){
 28     used[u]=true;
 29     for(int i=0;i<G[u].size();++i){
 30         if(!used[G[u][i]])dfs(G[u][i]);
 31     }
 32     vs.push_back(u);
 33 }
 34 void rdfs(int u,int k){
 35     used[u]=true;
 36     cmp[u]=k;
 37     for(int i=0;i<rG[u].size();++i){
 38         if(!used[rG[u][i]])rdfs(rG[u][i],k);
 39     }
 40 }
 41 int scc(){
 42     memset(used,0,sizeof(used));
 43     vs.clear();
 44     for(int i=0;i<n;++i){
 45         if(!used[i])dfs(i);
 46     }
 47     memset(used,0,sizeof(used));
 48     int k =0;
 49     for (int i=vs.size()-1;i>=0;--i){
 50         if(!used[vs[i]])rdfs(vs[i],k++);
 51     }
 52     return k;
 53 }
 54 int s[maxn],t[maxn],d[maxn];
 55 void build(){
 56     for(int i=0;i<m;++i){
 57         for(int j=0;j<i;++j){
 58                 if(min(s[i]+d[i],s[j]+d[j])>max(s[i],s[j])){
 59                     //开始与开始冲突 xi->^xj&&xj->^xi
 60                     addedge(i,j+m);
 61                     addedge(j,i+m);
 62                 }
 63                 if(min(s[i]+d[i],t[j])>max(s[i],t[j]-d[j])){
 64                     //开始与结束冲突 xi->xj&&^xj->^xi
 65                     addedge(i,j);
 66                     addedge(j+m,i+m);
 67                 }
 68                 if(min(t[i],s[j]+d[j])>max(t[i]-d[i],s[j])){
 69                     //结束与开始冲突 ^xi->^xj&&xj->xi
 70                     addedge(i+m,j+m);
 71                     addedge(j,i);
 72                 }
 73                 if(min(t[i],t[j])>max(t[i]-d[i],t[j]-d[j])){
 74                     //结束与结束冲突 ^xi->xj&&^xj->xi
 75                     addedge(i+m,j);
 76                     addedge(j+m,i);
 77                 }
 78             }
 79     }
 80 }
 81 void solve(){
 82     build();
 83     int k =scc();
 84     for(int i=0;i<m;++i){
 85         if(cmp[i]==cmp[m+i]){
 86             printf("NO\n");
 87             return ;
 88         }
 89     }
 90     printf("YES\n");
 91     for(int i=0;i<m;++i){
 92         if(cmp[i]>cmp[i+m]){
 93             printf("%02d:%02d %02d:%02d\n",s[i]/60,s[i]%60,(s[i]+d[i])/60,(s[i]+d[i])%60);
 94         }
 95         else printf("%02d:%02d %02d:%02d\n",(t[i]-d[i])/60,(t[i]-d[i])%60,t[i]/60,t[i]%60);
 96     }
 97 }
 98 int main (){
 99     while(scanf("%d",&m)!=EOF){
100         init();
101         n = 2*m;
102         int sh,sm,th,tm;
103         for(int i=0;i<m;++i){
104             scanf("%d:%d %d:%d %d",&sh,&sm,&th,&tm,&d[i]);
105             s[i]=sh*60+sm;
106             t[i]=th*60+tm;
107         }
108         solve();
109     }
110 }
View Code

 


联系
我们