闭会算法好题之 2020ICPC 澳门站签到 A 题

#include<bits/stdc++.h>#define endl '\n'using namespace std;int n,m;#define MAX 100009vector<vector<pair<int,int> > >v(MAX);vector<int>ans;int d[MAX];bool vis[MAX];int dsu(int num){    if(num==d[num])        return num;    return d[num]=dsu(d[num]);}int connect(int a,int b){    int ma=dsu(a);    int mb=dsu(b);    if(ma==mb)        return -1;    else    {        d[ma]=mb;        return 0;    }}int dfs(int node,int st,int ed){    int i,j,flag=0,num;    for(i=0;i<v[node].size();i++)    {        int nx=v[node][i].first;        if(nx==ed)        {            ans.push_back(v[node][i].second);            return nx;        }        if(vis[nx]==0)        {            vis[nx]=1;            num= dfs(nx,st,ed);            if(num!=-1)            {                ans.push_back(v[node][i].second);                if(node!=st)                    return node;                else                    return -1;            }            vis[nx]=0;        }    }    return -1;}int main(){    int i,j,t;    ios::sync_with_stdio(false);    cin.tie(0),cout.tie(0);    cin>>t;    while(t--)    {        cin>>n>>m;        ans.clear();        for(i=1;i<=n;i++)        {            d[i]=i;            v[i].clear();            vis[i]=0;        }        int ok=1;        for(i=0;i<m;i++)        {            int a,b;            cin>>a>>b;            if(ok)            {                int res=connect(a,b);                if(res==-1)                {                    dfs(a,a,b);                    if(ans.size()!=0)                        ans.push_back(i+1);                    ok=0;                }                v[a].push_back(make_pair(b,i+1));                v[b].push_back(make_pair(a,i+1));            }        }        if(ans.size()!=0)        {            sort(ans.begin(),ans.end());            cout<<ans[0];            for(i=1;i<ans.size();i++)                cout<<" "<<ans[i];            cout<<endl;        }        else            cout<<-1<<endl;     }    return 0;}/*16 81 21 21 22 35 63 42 55 4*/