E. Reachability from the Capital

这个题目就是给你一个有向图，给你起点，问增加多少条边让这个图变成一个连通图。

这个因为n只有5000m只有5000

所以可以暴力枚举这个n，用n*n的复杂度过去。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <map>
#include <string>
#include <cstring>
#include <bitset>
using namespace std;
const int maxn=5e3+10;
vector<int>G[maxn];
bool vis[maxn];
bool cnt[maxn];
int ans=0;
void dfs(int u,int f){
    ans++;
    vis[u]=1;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==f||vis[v]) continue;
        dfs(v,u);
    }
}
 
int num;
void DFS(int u,int f){
    if(vis[u]) return ;
    num++;
    cnt[u]=1;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==f||vis[v]||cnt[v]) continue;
        DFS(v,u);
    }
}
vector<int>a;
int main(){
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
    }
    dfs(s,-1);
    for(int i=1;i<=n;i++){
        if(!vis[i]) a.push_back(i);
    }
    int res=0;
    while(ans<n){
        int maxs=0,id=-1;
        for(int i=0;i<a.size();i++){
            memset(cnt,0,sizeof(cnt));
            num=0;
            int x=a[i];
            DFS(x,-1);
            if(num>maxs) maxs=num,id=x;
        }
        if(id==-1) break; 
        res++;
        dfs(id,-1);
    }
    printf("%d\n",res);
    return 0;
}
 

未优化

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <map>
#include <string>
#include <cstring>
#include <bitset>
using namespace std;
const int maxn=5e3+10;
vector<int>G[maxn];
bool vis[maxn];
bool cnt[maxn];
int ans=0;
void dfs(int u,int f){
    ans++;
    vis[u]=1;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==f||vis[v]) continue;
        dfs(v,u);
    }
}
 
int num;
void DFS(int u,int f){
    if(vis[u]) return ;
    num++;
    cnt[u]=1;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==f||vis[v]||cnt[v]) continue;
        DFS(v,u);
    }
}
 
void dfs2(int u,int f){
    if(vis[u]) return ;
    cnt[u]=0;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==f||vis[v]||cnt[v]==0) continue;
        dfs2(v,u);
    }
}
 
vector<int>a;
int main(){
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
    }
    dfs(s,-1);
    for(int i=1;i<=n;i++){
        if(!vis[i]) a.push_back(i);
    }
    int res=0;
    while(ans<n){
        int maxs=0,id=-1;
        for(int i=0;i<a.size();i++){
            num=0;
            int x=a[i];
            DFS(x,-1);
            dfs2(x,-1);
            if(num>maxs) maxs=num,id=x;
        }
        if(id==-1) break; 
        res++;
        dfs(id,-1);
    }
    printf("%d\n",res);
    return 0;
}
 
 

dfs优化memset

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <map>
#include <string>
#include <cstring>
#include <bitset>
using namespace std;
const int maxn=5e3+10;
vector<int>G[maxn];
bool vis[maxn];
bool cnt[maxn];
int ans=0;
void dfs(int u,int f){
    ans++;
    vis[u]=1;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==f||vis[v]) continue;
        dfs(v,u);
    }
}
 
int num;
void DFS(int u,int f){
    if(vis[u]) return ;
    num++;
    cnt[u]=1;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==f||vis[v]||cnt[v]) continue;
        DFS(v,u);
    }
}
 
void dfs2(int u,int f){
    if(vis[u]) return ;
    cnt[u]=0;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v==f||vis[v]||cnt[v]==0) continue;
        dfs2(v,u);
    }
}
 
vector<int>a;
int main(){
    int n,m,s;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
    }
    dfs(s,-1);
    for(int i=1;i<=n;i++){
        if(!vis[i]) a.push_back(i);
    }
    int res=0;
    while(ans<n){
        int maxs=0,id=-1;
        for(int i=0;i<a.size();i++){
            num=0;
            int x=a[i];
            DFS(x,-1);
            dfs2(x,-1);
            if(num>maxs) maxs=num,id=x;
        }
        if(id==-1) break; 
        res++;
        dfs(id,-1);
    }
    printf("%d\n",res);
    return 0;
}
 
 

memset优化