http://codeforces.com/problemset/problem/999/E

題意 有向圖??? 給你n個點，m條邊，以及一個初始點s，問你至少還需要增加多少條邊，使得初始點s與剩下其他的所有點都連通。

第一個想法自然是通過上標記的方法，對每一個入度為0的點跑dfs。

但是問題在于剩下沒有上標記的點，是成環的點。這些點不能有效的形成我們希望的拓撲序。

第一個想法是可以考慮上特殊標記，順序枚舉每個環上的點跑dfs，對每個隨機跑的點上標記，在dfs的過程中如果可以經過之前枚舉跑到的起點，就去掉這個點的標記，隨后統計特殊標記的數量，經過測試，確實可以AC

#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; const double eps = 1e-9; const int maxn = 5010; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,tmp,K,s; bool vis[maxn]; bool vis2[maxn]; bool vis3[maxn]; int ind[maxn]; struct Edge{int to,next; }edge[maxn]; int head[maxn],tot,ans; void init(){Mem(head,0);tot = 0; } void add(int u,int v){edge[++tot].next = head[u];edge[tot].to = v;head[u] = tot; } void dfs(int t){vis[t] = 1;for(int i = head[t]; i;i = edge[i].next){int v = edge[i].to;if(vis[v]) continue;dfs(v);} } void dfs2(int t){vis3[t] = 1;vis[t] = 1;for(int i = head[t];i;i = edge[i].next){int v = edge[i].to;if(vis2[v]){vis2[v] = 0;ans--;}if(vis3[v]) continue;dfs2(v);} } int main() {scanf("%d%d%d",&N,&M,&s);init();For(i,1,M){int u,v;scanf("%d%d",&u,&v);add(u,v);ind[v]++;}dfs(s);ans = 0;For(i,1,N){if(!ind[i] && !vis[i]){ans++;dfs(i);}}For(i,1,N){if(!vis[i]){Mem(vis3,0);ans++;dfs2(i);vis2[i] = 1;}}Pri(ans);#ifdef VSCodesystem("pause");#endifreturn 0; } View Code

第二個想法是標記覆蓋，順序dfs每一個點，以每一個點為起點經過的點用不同標記覆蓋，最后判斷所有標記的數量

#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; const double eps = 1e-9; const int maxn = 5010; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,tmp,K,s; int vis[maxn]; bool vis2[maxn]; bool vis3[maxn]; int ind[maxn]; struct Edge{int to,next; }edge[maxn]; int head[maxn],tot,ans; void init(){Mem(head,0);tot = 0; } void add(int u,int v){edge[++tot].next = head[u];edge[tot].to = v;head[u] = tot; } void dfs(int t){vis[t] = tmp;for(int i = head[t]; i;i = edge[i].next){int v = edge[i].to;if(vis[v] == tmp) continue;dfs(v);} } int main() {scanf("%d%d%d",&N,&M,&s);init();For(i,1,M){int u,v;scanf("%d%d",&u,&v);add(u,v);}tmp = 1;dfs(s);For(i,1,N){if(!vis[i]){tmp++;dfs(i);}}ans = 0;vis2[1] = 1;For(i,1,N){if(!vis2[vis[i]]){vis2[vis[i]] = 1;ans++;}}Pri(ans);#ifdef VSCodesystem("pause");#endifreturn 0; } View Code

當然，以上兩個算法都是O(n2)的算法，這題5000的數據范圍可以跑，但是當數據范圍擴大的時候，就需要考慮更強的算法來解決；

用Tarjan算法將原圖縮點變成一個可拓撲的dag圖，直接數入度為0的點即可。

#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x) #define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; const double eps = 1e-9; const int maxn = 5010; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,tmp,K,s; int vis[maxn]; struct Edge{int to,next; }edge[maxn]; int head[maxn],tot,ans; int Low[maxn],dfn[maxn],Stack[maxn],belong[maxn]; int index,top,scc; bool Instack[maxn]; int ind[maxn]; int num[maxn]; void Tarjan(int u){int v;Low[u] = dfn[u] = ++ index;Stack[top++] = u;Instack[u] = true;for(int i = head[u];i;i =edge[i].next){int v = edge[i].to;if(!dfn[v]){Tarjan(v);if(Low[u] > Low[v]) Low[u] = Low[v];}else if(Instack[v] && Low[u] > dfn[v]){Low[u] = dfn[v];}}if(Low[u] == dfn[u]){scc++;do{v = Stack[--top];Instack[v] = false;belong[v] = scc;num[scc]++;}while(v != u);} } void init(){Mem(head,0);tot = 0; } void add(int u,int v){edge[++tot].next = head[u];edge[tot].to = v;head[u] = tot; }int main() {scanf("%d%d%d",&N,&M,&s);init();For(i,1,M){int u,v;scanf("%d%d",&u,&v);add(u,v);}index = scc = top = 0;For(i,1,N) if(!dfn[i]) Tarjan(i);int ans = 0;For(i,1,N){for(int j = head[i];j;j = edge[j].next){int v = edge[j].to;if(belong[i] != belong[v]){ind[belong[v]] = 1;}}}vis[belong[s]] = 1;For(i,1,N){if(!ind[belong[i]] && !vis[belong[i]]){vis[belong[i]] = 1;ans++;}}Pri(ans);#ifdef VSCodesystem("pause");#endifreturn 0; }

?

轉載于:https://www.cnblogs.com/Hugh-Locke/p/9595021.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的CodeForces999E 双dfs // 标记覆盖 // tarjan缩点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。