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-;
const int maxn = ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ;
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,);
tot = ;
}
void add(int u,int v){
edge[++tot].next = head[u];
edge[tot].to = v;
head[u] = tot;
}
void dfs(int t){
vis[t] = ;
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] = ;
vis[t] = ;
for(int i = head[t];i;i = edge[i].next){
int v = edge[i].to;
if(vis2[v]){
vis2[v] = ;
ans--;
}
if(vis3[v]) continue;
dfs2(v);
}
}
int main()
{
scanf("%d%d%d",&N,&M,&s);
init();
For(i,,M){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
ind[v]++;
}
dfs(s);
ans = ;
For(i,,N){
if(!ind[i] && !vis[i]){
ans++;
dfs(i);
}
}
For(i,,N){
if(!vis[i]){
Mem(vis3,);
ans++;
dfs2(i);
vis2[i] = ;
}
}
Pri(ans);
#ifdef VSCode
system("pause");
#endif
return ;
}
第二个想法是标记覆盖，顺序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-;
const int maxn = ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ;
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,);
tot = ;
}
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,,M){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
tmp = ;
dfs(s);
For(i,,N){
if(!vis[i]){
tmp++;
dfs(i);
}
}
ans = ;
vis2[] = ;
For(i,,N){
if(!vis2[vis[i]]){
vis2[vis[i]] = ;
ans++;
}
}
Pri(ans);
#ifdef VSCode
system("pause");
#endif
return ;
}
当然，以上两个算法都是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-;
const int maxn = ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ;
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,);
tot = ;
}
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,,M){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
index = scc = top = ;
For(i,,N) if(!dfn[i]) Tarjan(i);
int ans = ;
For(i,,N){
for(int j = head[i];j;j = edge[j].next){
int v = edge[j].to;
if(belong[i] != belong[v]){
ind[belong[v]] = ;
}
}
}
vis[belong[s]] = ;
For(i,,N){
if(!ind[belong[i]] && !vis[belong[i]]){
vis[belong[i]] = ;
ans++;
}
}
Pri(ans);
#ifdef VSCode
system("pause");
#endif
return ;
}