题目链接:

题意:给定一个强联通分量,m条边,n个点,需要删去m-2*n个边,使得图仍为强连通分量

题解:因强连通分量两点间任意可达,所以处理出,从1结点到各个节点所需要的边和从其他结点到达1结点所需要的边就好了

正着dfs和建反向图dfs即可找到2n-2条边,

百度题解的时候发现了这个,正反dfs求强连通分量,

#include
     
      using namespace std;typedef pair
      
       pii;int t,n,m;const int N=1e5+10;vector
       
        g[N],g1[N];int vis[N];set
        
         all;vector
         
          vv;void dfs1(int u){    vis[u]=1;    for(auto v:g[u]){        if(vis[v]) continue;        vv.push_back({u,v});        dfs1(v);    }}void dfs2(int u){    vis[u]=1;    for(auto v:g1[u]){        if(vis[v]) continue;        vv.push_back({v,u});        dfs2(v);    }}int main(){    int x,y;scanf("%d",&t);    while(t--){        scanf("%d%d",&n,&m);        vv.clear();all.clear();        for(int i=1;i<=n;i++) g[i].clear(),g1[i].clear(),vis[i]=0;        for(int i=1;i<=m;i++){            scanf("%d%d",&x,&y);            g[x].push_back(y);all.insert({x,y});            g1[y].push_back(x);        }        dfs1(1);        for(int i=1;i<=n;i++) vis[i]=0;         dfs2(1);        for(auto v:vv) all.erase(v);        int num=m-2*n;        for(auto v:all){            printf("%d %d\n",v.first,v.second);            num--;            if(num==0) break;        }    }    return 0;}