题意:
题目给出一幅有向图,由 (n) 个点 (m) 条边组成,且保证是强连通图,让你删去 (m-2 imes n) 条边。
想法:
-
建两幅图,一幅为正常图,一幅为反图,然后选择一个点对两幅图都进行一次 (dfs),然后只要是没访问到的边就是这个强连通图中多余的边。
-
这样子就是相当于,正常图 (dfs) 满足了 (pos) 可达其他所有点,反图 (dfs) 满足了其他所有点均可达 (pos) 点,那么由两次 (dfs) 经过的边就是强联通图。
代码:
struct node{
int u,v;
}s[maxn];
struct node1{
int u,v;
}s1[maxn];
vector<int>g[maxn];
vector<int>g1[maxn];
int vis[maxn];
int vis1[maxn];
map<pair<int,int>,int>mp;
map<pair<int,int>,int>mp1;
void dfs(int u)
{
vis[u]=1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(vis[v]==0){
mp[make_pair(u,v)]=1;
dfs(v);
}
}
}
void dfs1(int u)
{
vis1[u]=1;
for(int i=0;i<g1[u].size();i++){
int v=g1[u][i];
if(vis1[v]==0){
mp[make_pair(v,u)]=1;
dfs1(v);
}
}
}
int main()
{
int T;
cin>>T;
while(T--){
int n,m;
mp.clear();
mem(vis,0);
mem(vis1,0);
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++){
g[i].clear();
g1[i].clear();
}
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
s[i].u=u;
s[i].v=v;
g[u].push_back(v);
s1[i].u=v;
s1[i].v=u;
g1[v].push_back(u);
}
dfs(1);
dfs1(1);
int sum=m-2*n;
for(int i=1;i<=m;i++){
if(sum==0)break;
if(mp[make_pair(s[i].u,s[i].v)]!=1){
printf("%d %d
",s[i].u,s[i].v);
sum--;
}
}
}
return 0;
}