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 ", x) #define Prl(x) printf("%lld ",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 VSCode system("pause"); #endif return 0; }
第二个想法是标记覆盖，顺序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 ", x) #define Prl(x) printf("%lld ",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 VSCode system("pause"); #endif return 0; }
当然，以上两个算法都是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 ", x) #define Prl(x) printf("%lld ",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 VSCode system("pause"); #endif return 0; }