题目就是求一副图的割边，然后对于那些有重复的边的，不能算做割边。
思路就是每次加入一条边的时候，判断这条边是否存在过，存在过的话，就把那条边设为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=100000+20; struct data { int u,v,id; int next; } e[maxn*2]; int first[10000+20]; 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[10000+20];//??????? int low[10000+20];//???????? 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,0,sizeof(DFN)); memset(low,0,sizeof(low)); memset (first,0,sizeof first); when=0; num=0; return ; } int n,m; void work () { init (); for (int i=1; i<=m; i++) { int u,v; scanf ("%d%d",&u,&v); add(u,v,i); add(v,u,i); } root=1;//???? dfs(1,root); printf ("%d ",pr.size()); for (set<int>::iterator it= pr.begin(); it!=pr.end(); ++it) { printf ("%d ",*it); } printf (" "); return ; } int main () { while (scanf ("%d%d",&n,&m)!=EOF) work (); return 0; }
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=100000+20; struct data { int u,v,id; int next; } e[maxn*2]; int first[10000+20]; 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[10000+20];//第几个被访问到 int low[10000+20];//最厉害能访问到谁 int used[10000 + 20]; int togo[10000 + 20]; 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, 0, sizeof togo); memset(used, 0, sizeof used); pr.clear(); memset(DFN,0,sizeof(DFN)); memset(low,0,sizeof(low)); memset (first,0,sizeof first); when=0; num=0; return ; } int n,m; void work () { init (); for (int i=1; i<=m; i++) { int u,v; scanf ("%d%d",&u,&v); add(u,v,i); add(v,u,i); } for (int i = 1; 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=1;//从根节点 dfs(1,root); printf ("%d ",pr.size()); for (set<int>::iterator it= pr.begin(); it!=pr.end(); ++it) { printf ("%d ",*it); } printf (" "); return ; } int main () { #ifdef local freopen("data.txt", "r", stdin); #endif while (scanf ("%d%d",&n,&m)!=EOF) work (); return 0; }