题目就是求一副图的割边，然后对于那些有重复的边的，不能算做割边。
思路就是每次加入一条边的时候，判断这条边是否存在过，存在过的话，就把那条边设为inf，表示不能作为割边。于是有了这样的代码
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string> const int maxn=+;
struct data {
int u,v,id;
int next;
} e[maxn*];
int first[+];
int num;//??????
bool isok (int u,int v) {
//???u????????????
for (int i=first[u]; i; i=e[i].next) {
if (e[i].v==v) {
e[i].id=inf;
return false;
}
}
return true;
}
void add (int u,int v,int id) {
if (!isok(u,v)) return ;//???????????????
++num;
e[num].u=u;
e[num].v=v;
e[num].id=id;
e[num].next=first[u];
first[u]=num;
return ;
}
int DFN[+];//???????
int low[+];//????????
int when;//?????????
int root;
set<int>pr;
void dfs (int cur,int father) {
++when;
DFN[cur]=when;
low[cur]=when;
for (int i=first[cur]; i; i=e[i].next) {
int v=e[i].v;//cur????v???
if (!DFN[v]) { //??????
dfs(v,cur);
low[cur]=min(low[cur],low[v]);
if (low[v]>DFN[cur]&&e[i].id!=inf) {
pr.insert(e[i].id);
}
} else if(v!=father) {
low[cur]=min(low[cur],DFN[v]);
}
}
return ;
}
void init () {
pr.clear();
memset(DFN,,sizeof(DFN));
memset(low,,sizeof(low));
memset (first,,sizeof first);
when=;
num=;
return ;
}
int n,m;
void work () {
init ();
for (int i=; i<=m; i++) {
int u,v;
scanf ("%d%d",&u,&v);
add(u,v,i);
add(v,u,i);
}
root=;//????
dfs(,root);
printf ("%d\n",pr.size());
for (set<int>::iterator it= pr.begin(); it!=pr.end(); ++it) {
printf ("%d ",*it);
}
printf ("\n");
return ;
}
int main () {
while (scanf ("%d%d",&n,&m)!=EOF) work ();
return ;
}
240ms过的。但是应该会有些坑爹的图，卡到它TLE的。
所以这个方法不行
考虑去重，做到O（m）
用used[v] = u表示u--v这样有一条边了。
建立完整张图后，遍历一次，如果重复的话，就去掉就行了。used数组不用清空，因为值u肯定是不同的。
坑就是出现了两次，才能判断第二条边重复了。那么第一条边怎么设置为inf呢？
方法就是用一个数组togo[v] = j表示，当前顶点v的上一条边是j。去重即可。
压缩时间为44ms
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string> const int maxn=+;
struct data {
int u,v,id;
int next;
} e[maxn*];
int first[+];
int num;//用到第几条边
bool isok (int u,int v) {
//问一下u顶点所有边能不能去这个点
for (int i=first[u]; i; i=e[i].next) {
if (e[i].v==v) {
e[i].id=inf;
return false;
}
}
return true;
}
void add (int u,int v,int id) {
// if (!isok(u,v)) return ;//判断是否有重复的边，绝对不是桥
++num;
e[num].u=u;
e[num].v=v;
e[num].id=id;
e[num].next=first[u];
first[u]=num;
return ;
}
int DFN[+];//第几个被访问到
int low[+];//最厉害能访问到谁
int used[ + ];
int togo[ + ];
int when;//什么时候被访问到的
int root;
set<int>pr;
void dfs (int cur,int father) {
++when;
DFN[cur]=when;
low[cur]=when;
for (int i=first[cur]; i; i=e[i].next) {
int v=e[i].v;//cur是爸爸，v是儿子
if (!DFN[v]) { //没访问过的话
dfs(v,cur);
low[cur]=min(low[cur],low[v]);
if (low[v]>DFN[cur]&&e[i].id!=inf) {
pr.insert(e[i].id);
}
} else if(v!=father) {
low[cur]=min(low[cur],DFN[v]);
}
}
return ;
}
void init () {
memset(togo, , sizeof togo);
memset(used, , sizeof used);
pr.clear();
memset(DFN,,sizeof(DFN));
memset(low,,sizeof(low));
memset (first,,sizeof first);
when=;
num=;
return ;
}
int n,m;
void work () {
init ();
for (int i=; i<=m; i++) {
int u,v;
scanf ("%d%d",&u,&v);
add(u,v,i);
add(v,u,i);
}
for (int i = ; i <= n; ++i) {
// memset(used, 0, sizeof used);
for (int j = first[i]; j; j = e[j].next) {
if (used[e[j].v] == e[j].u) {
e[j].id = inf;
e[togo[e[j].v]].id = inf;
}
used[e[j].v] = e[j].u;
togo[e[j].v] = j;
}
}
root=;//从根节点
dfs(,root);
printf ("%d\n",pr.size());
for (set<int>::iterator it= pr.begin(); it!=pr.end(); ++it) {
printf ("%d ",*it);
}
printf ("\n");
return ;
}
int main () {
#ifdef local
freopen("data.txt", "r", stdin);
#endif
while (scanf ("%d%d",&n,&m)!=EOF) work ();
return ;
}