Educational Codeforces Round 42 (Rated for Div. 2)F - Simple Cycles Edges

http://codeforces.com/contest/962/problem/F

求没有被两个及以上的简单环包含的边

解法：双联通求割顶，在bcc中看这是不是一个简单环，是的话把整个bcc的环加到答案中即可（正确性显然，因为bcc一定是环了，然后如果一个bcc不是简单环，那么所有边一定包含在两个简单环中）

//#pragma comment(linker, "/stack:200000000")

//#pragma GCC optimize("Ofast,no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define vi vector<int>

#define mod 1000000007

#define C 0.5772156649

#define ls l,m,rt<<1

#define rs m+1,r,rt<<1|1

#define pil pair<int,ll>

#define pli pair<ll,int>

#define pii pair<int,int>

#define cd complex<double>

#define ull unsigned long long

#define base 1000000000000000000

#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

vector<pii>v[N];

int dfn[N],low[N];

int ind,iscut[N],n,m;

vi ans;

struct edge{int u,v,id;};

stack<edge>s;

int bcccnt,bccno[N],ed[N];

vi bcc[N],bb[N];

void tarjan(int u,int f)

{

    dfn[u]=low[u]=++ind;

    int ch=;

    for(int i=;i<v[u].size();i++)

    {

        int x=v[u][i].fi;

        if(x==f)continue;

        edge e={u,x,v[u][i].se};

        if(!dfn[x])

        {

            s.push(e);

            ch++;

            tarjan(x,u);

            low[u]=min(low[u],low[x]);

            if(low[x]>=dfn[u])

            {

                iscut[u]=;

                bcccnt++;

                bcc[bcccnt].clear();

                while()

                {

                    edge now=s.top();s.pop();

                    ed[bcccnt]++;bb[bcccnt].pb(now.id);//printf("%d++++%d\n",bcccnt,now.id);

                    if(bccno[now.u]!=bcccnt){bcc[bcccnt].pb(now.u);bccno[now.u]=bcccnt;}

                    if(bccno[now.v]!=bcccnt){bcc[bcccnt].pb(now.v);bccno[now.v]=bcccnt;}

                    if(now.u==u&&now.v==x)break;

                }

            }

        }

        else if(dfn[x]<dfn[u])

        {

            s.push(e);

            low[u]=min(low[u],dfn[x]);

        }

    }

    if(f<&&ch==)iscut[u]=;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)

    {

        int a,b;scanf("%d%d",&a,&b);

        v[a].pb(mp(b,i)),v[b].pb(mp(a,i));

    }

    ind=;

    for(int i=;i<=n;i++)

        if(!dfn[i])

            tarjan(i,-);

//    for(int i=1;i<=n;i++)printf("%d ",bccno[i]);puts("");

    memset(dfn,,sizeof dfn);

    for(int i=;i<=bcccnt;i++)

    {

        if(ed[i]==bcc[i].size()&&ed[i])

        {

            for(int j=;j<bb[i].size();j++)ans.pb(bb[i][j]);

        }

    }

    sort(ans.begin(),ans.end());

    printf("%d\n",ans.size());

    for(int i=;i<ans.size();i++)printf("%d ",ans[i]);

    puts("");

    return ;

}

/***********************

5 6

1 2

1 3

2 3

3 4

4 5

3 5

***********************/