codeforces 962F.simple cycle（tarjan/点双连通分量）

题目连接：http://codeforces.com/contest/962/problem/F

题目大意是定义一个simple cycle为从一个节点开始绕环走一遍能经过simple cycle内任何一个节点，并且不超过一次。

因为是无向图，而且是环，即为连通分量，所以模型转化为求点双连通分量，依据题意求得的点双连通分量需要满足题目simple cycle的定义，所以当一个点双连通分量的边数量和点数量相等时才能构成simple cycle，在tarjan求割点的时候，需要存储点双联通分量的点和边的数量，最后判断一下是否相等，整体存储起来，最终排序一下满足题意的input边的目录。

AC代码:

#include<iostream>

#include<stack>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

using namespace std;

const int maxn = 1e5+7;

struct node{

    vector<int> vex;

    vector<int> num;

};//建图 vex为node[i]连接的节点，num储存node[i]和vex内节点连接边的序号

struct edge{

    int a,b,id;

}E[maxn*2];//a为边的起点，b为边的终点，id为边的输入目录

stack<int> stk;//储存边的目录的栈

node g[100005];

int n,m,tot;

int BCC = 0;//统计BCC

int visit[200014],dfn[100005],low[100005],iscut[100005];

int bcc[100005];

vector<int> ans;

void tarjan(int x,int fa){

    int child = 0;

    low[x] = dfn[x] = ++tot;

    for(int i = 0;i<g[x].vex.size() ;i++){

        int tedge = g[x].num[i]; //边序号，后续可以由边序号作为索引找到该边的id（目录）

        int temp = E[tedge].b;//temp为边的终点

        if(temp == fa){

            continue;

        }

        if(visit[tedge]){

            continue;

        }

        visit[tedge] = visit[tedge^1] = 1;//标记双向边已经访问过

        stk.push(tedge);

        if(!dfn[temp]){

            child++;

            tarjan(temp,x);

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

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

            {//找到割点，即找到一个点双连通分量

                iscut[x] = 1;

                BCC++;

                set<int> Vset;//存该BCC的点

                set<int> Eset;// 存该BCC的边

                Vset.insert(x);

                int s;

                do{

                    s = stk.top();

                    stk.pop();

                    Eset.insert(E[s].id);//加入边的目录id

                    Vset.insert(E[s].b);//加入边的终点

                }while(s!=tedge);

                if(Eset.size() == Vset.size()){

                    for(set<int>::iterator it=Eset.begin();it!=Eset.end();it++)

                        ans.push_back(*it);//以题意要求判断是否为simple cycle

                }

            }

        }

        else

        {

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

        }

    }

    if(fa == -1 && child <2){

        iscut[x] = 0;

    }

}

int edgenum = 0;//边的序号从0开始，因为是建立双向边所以两条边标记的序号是异或关系，由边序号可以找到该边的id

void addedge(int u,int v,int id){

    E[edgenum].a = u;

    E[edgenum].b = v;

    g[u].num.push_back(edgenum);

    E[edgenum++].id = id;

}

int main(){

    int n,m;

    cin>>n>>m;

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

        int u,v;

        cin>>u>>v;

        addedge(u,v,i);

        addedge(v,u,i);

        g[u].vex.push_back(v);

        g[v].vex.push_back(u);

    }

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

        if(!dfn[i]){

            tarjan(i,-1);

        }

    }

    int cut = 0;

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

        if(iscut[i] == 1){

            cut++;

        }

    }

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

    cout<<ans.size()<<endl;

    for(int i=0;i<(int)ans.size();i++)

        cout<<ans[i]<<" ";

    //cout<<BCC<<" "<<cut;

    return 0;

}

巴特西

codeforces 962F.simple cycle（tarjan/点双连通分量）

最新文章

热门文章