双连通分量+二分图 boj1410 lucky cities

Lucky citiesSubmit: 49   Accepted:14Time Limit: 5000MS  Memory Limit: 65536KDescription
John has recently arrived in Romania for the South Eastern European Regional competitions. John has never been to Romania before so Romanians decided to organize sightseeing tour for him. This tour will include several Romanian cities and none of them will be visited more than once. John will start in one city and will visit some other cities according to a guide tour. At the end of the tour John will return to the starting point.
There are N cities numbered from 1 to N and M two-way roads in the country. Each road connects two different cities. Consider a sightseeing tour for John c1,c2, ...,cn, where each ci denotes a city in Romania. Then all ci must be distinct, ci and ci+1 must be connected by a road, where i=1,2,...,n-1, cn and c1 must be connected by a road as well.
Being a odd person John would like to visit an odd number of cities. The organizers have drawn the plan of all possible tours with an odd number of cities.
Residents of the cities would like John to visit them. So if there is at least one tour passing through some city than this city is called lucky. Your task is to calculate the number of lucky cities in Romania.


Input
The first line of input contains a single integer T – a number of test cases. Every test case starts with a line containing two integers separated by a single space – N and M. Each of the next M lines will contain two integers ai and bi separated by a single space – the labels of cities that i-th road connects.
1 ≤ T ≤ 77, 0 ≤ N, M ≤ 100000 (10⁵), 1 ≤ ai < bi ≤ N.

Output
Output should contain T lines – answers for each of the test cases.

Sample Input

1
7 7
1 5
3 5
3 7
1 7
6 7
4 7
4 6


Sample Output

3


Source
Southeastern European 2008

题意描述：
从城市A出发，经过奇数个点回到A城市，这些经过的城市叫做lucky city，计算这个图中的lucky city的数量。

解体思路：
寻找一个圈(可以看作无向图的双连通分量，这个双连通分量中的节点是奇数个)
下面的连接给出了类似题的解体思路：
http://bbs.ecust.edu.cn/viewthread.php?tid=229244&page=1#pid4419148
不过其中求双连通分量的伪代码有一处错误，看下面代码的注释

void pbc_dfs(int u, int parent) {


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

foreach e in adjacent list [u] {

v = e->v;

if (v != parent && dfn[v] < dfn[u]) {

stack.push(Edge(u, v));

/*v已经访问过了，如果v是u的祖先节点，则更新low[u]值*/

if (0 != dfn[v]) low[u] = min(low[u], dfn[v])

else {

pbc_dfs(v, u);

/*递归之后，如果low[v]值减小了，也就是v有指向它祖先节点的边，那么它的low值将减小，同时需要更新v的父节点u的low值*/

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

/*这里的判断应该改为low[v] >= dfn[u]i,说明v没有边回到u或者u的祖先节点，那么包括v的这个子树就构成了一个双连通分量*/
/*并且这个判断条件直到回溯到圈的最上层的节点处才成立，这时就能弹出所有位于圈中的边*/

if (dfn[u] >= low[v]) { // u is a cut point

do {

Edge edg = stack.pop();

...(some operation)

} while(edg is not uv);

++component_id;

}

}

}

}



参考下面的证明：

1. 求出所有点双连通分量后就是要求每个点双连通分量中的点是否在某个奇数顶点的圈中, 这里需
   
2. 要用到两条定理:
   
3. 1. 一个点双连通分量中如果存在一个奇数顶点的圈, 那么此分量的所有点都在某个奇数圈中.
   
4. 2. 一个点双连通分量有奇数圈, 与这个分量不是二分图等价.
   
5. 
   
6. 直观的证明:
   
7. 1. 若此分量有奇数个点, 那么由于此分量中一定有一条回路连接所有点, 所以得证; 若此分量
   
8. 中有偶数个点, 那么如果有一个奇数点的圈, 那么剩余点一定是奇数个, 剩余的点要么能依靠
   
9. 这个圈以外的边够成奇数顶点圈, 要么它需要依靠已有的奇数顶点圈上的边够成一个圈, 又在奇
   
10. 数顶点的圈上任取两点一定可以把圈分成奇数点和偶数点的两部分, 取偶数点的那部分与剩下的
    
11. 点结合就一定能构成另一个奇数顶点的圈.
    
12. 2. 反证法, 若此分量为二分图, 那么从一个点出发一定要经过偶数条边才能回来, 这是显然,
    
13. 的想像在河的一边出发总要过偶数次河才能回到原来的一边.
    
14. 
    
15. 这样只要判断每个分量是否是二分图即可, 用DFS或BFS对相邻点染黑白两色, 相邻点不同色,
    
16. 若遇到已染色且与当前点颜色相同则不是二分图(1).

我的代码，测试了好几天，个人觉得是没有问题的了，但是就是WA，相当郁闷。
题意中没有说明是否在存在a,a这种边，或是a,b之间是否有重边，个人觉得问题很可能出在这里。

还有就是在递归的时候可能爆栈，需要将tarjan()函数中的局部变量尽可能的改成局部变量。

#include <iostream>
#include <deque>
#include <string.h>
using namespace std;

#define SIZE 100010
#define MIN(a, b) ((a) < (b) ? (a) : (b))

typedef struct _edg
{
    int b, e;
}ST_EDGDS;

typedef struct _node
{
    int node;
    int next;
}ST_NODE;

ST_NODE cities[3 * SIZE];
int front[SIZE], rear[SIZE], DFN[SIZE], LOW[SIZE], bin_color[SIZE], Dindex, Lenght, ret;
deque<ST_EDGDS> Qedgs, Qconneted;
bool used[SIZE];


/*以邻接表存储边*/

void add_edg(int ai, int bi)
{
    /* a new beginning node */
    if (0 == front[ai] && 0 == rear[ai])
    {
        front[ai] = rear[ai] = ++Lenght;
        cities[Lenght].node = ai;
    }
    cities[rear[ai]].next = ++Lenght;
    rear[ai] = Lenght;
    cities[Lenght].node = bi;
}


/*判断是否有奇数圈*/
int chk_odd()
{
    int size, ai, bi, w = 1;
    ST_EDGDS st_edg;

// size = Qconneted.size() + 1;

    deque<ST_EDGDS>::iterator begin, end;
    end = Qconneted.end();
// if (0 == size % 2)

    {
        memset(bin_color, 0, sizeof(bin_color));
        for (begin = Qconneted.begin() ; begin != end ; begin++)
        {
            st_edg = *begin;
            ai = st_edg.b;
            bi = st_edg.e;
            if (0 == bin_color[ai] && 0 == bin_color[bi])
            {
                bin_color[ai] = w;
                bin_color[bi] = 0 - bin_color[ai];
            }
            else if (0 == bin_color[ai] && 0 != bin_color[bi])
                bin_color[ai] = 0 - bin_color[bi];
            else if (0 != bin_color[ai] && 0 == bin_color[bi])
                bin_color[bi] = 0 - bin_color[ai];
            else if (bin_color[ai] == bin_color[bi])
                goto cnt;
        }

        /*返回－1，说明这是个二分图，不存在奇数圈*/
        return -1;
    }

cnt:
    int add = 0;
    for (begin = Qconneted.begin() ; begin != end ; begin++)
    {
        st_edg = *begin;
        ai = st_edg.b;
        bi = st_edg.e;
        if (0 == used[ai])
        {
            add++;
            used[ai] = 1;
        }
    }
    
    return add;
}

int head_idx;
ST_EDGDS st_edg;
void tarjan(int crt_nd, int p_nd)
{
    int next_nd, next_idx;
    DFN[crt_nd] = LOW[crt_nd] = ++Dindex;
    head_idx = front[crt_nd];
    next_idx = cities[head_idx].next;

    for ( ; 0 != next_idx ; next_idx = cities[next_idx].next)
    {
        next_nd = cities[next_idx].node;
        /* means next_nd unvisited or have lower DFN, whatever, it's a new edg */
        if (next_nd != p_nd && DFN[next_nd] < DFN[crt_nd])
        {
            st_edg.b = crt_nd;
            st_edg.e = next_nd;
            Qedgs.push_front(st_edg);
            /* if next_nd visited, and have lower DFN */
            if (0 != DFN[next_nd])
                LOW[crt_nd] = MIN(LOW[crt_nd], DFN[next_nd]);
            else
            {
                tarjan(next_nd, crt_nd);
                LOW[crt_nd] = MIN(LOW[crt_nd], LOW[next_nd]);
                if (LOW[next_nd] >= DFN[crt_nd])
                {
                    int cnt = 0;
                    do
                    {
                        st_edg = Qedgs.front();
                        Qedgs.pop_front();
                        Qconneted.push_back(st_edg);
                        cnt++;
                    }while (!((st_edg.b == crt_nd && st_edg.e == next_nd) || (st_edg.b == next_nd && st_edg.e == crt_nd)));
                    /* check odd */
                    if (1 == cnt)
                    {
                        Qconneted.clear();
                        continue;
                    }
                    int add;
                    add = chk_odd();
                    if (-1 == add)
                    {
                        Qconneted.clear();
                        continue;
                    }
                    ret += add;
                    Qconneted.clear();
                }
            }
        }
    }
}

void solve(int size)
{
    int i;
    memset(DFN, 0 , sizeof(DFN));
    memset(LOW, 0, sizeof(LOW));
    /* from 1 to N */
    for (i=1 ; i<=size ; i++)
    {
        if (0 == DFN[i])
            tarjan(i, -1);
    }
}

int main(int argc, char *argv[])
{
    int T, N, M, i, ai, bi;
    cin >> T;
    while (T--)
    {
        Lenght = ret = Dindex = 0;
        memset(front, 0, sizeof(front));
        memset(rear, 0, sizeof(rear));
        memset(cities, 0, sizeof(cities));
        memset(used, 0, sizeof(used));
        Qedgs.clear();
        Qconneted.clear();
        cin >> N >> M;
        for (i=0 ; i<M ; i++)
        {
            scanf("%d %d", &ai, &bi);
            add_edg(ai, bi);
            add_edg(bi, ai);
        }
        solve(N);
        cout << ret << endl;
    }
}

这是另外一个代码，和上面最大的区别是：在tarjan()的时候将点入栈，而不是像上面的将边入栈。下面的这个代码在性能上远远不如上面的。具体原因待分析。

#include <iostream>
#include <deque>
#include <vector>
#include <string.h>
#include <bitset>
using namespace std;

vector<int> V[100010];
deque<int> Q, QMark, Q_bfs;
int DFN[100010], LOW[100010], Belong[100010], used[100010], bin_color[100010], Dindex, Bcnt, ret;
int w = 1, b = -1;
bitset<100010> bit_set;
bool isbin;

void clear(int cities)
{
    int i;
    for (i=0 ; i<=cities ; i++)
        V[i].clear();
    Q.clear();
}

int mark_used()
{
    int edg, add = 0;
    while (!QMark.empty())
    {
        edg = QMark.front();
        QMark.pop_front();
        if (0 == used[edg])
        {
            used[edg] = 1;
            add++;
        }
    }
    return add;
}

/*
void dfs(int edg)
{
    int color, next;
    vector::iterator begin, end;
    end = V[edg].end();
    color = bin_color[edg];
    for (begin = V[edg].begin() ; begin != end ; begin++)
    {
        next = *begin;
        if (!bit_set.test(next))
            continue;
        if (color == 0 - bin_color[next])
            continue;
        if (color == bin_color[next])
        {
            isbin = false;
            return ;
        }
        bin_color[next] = 0 - color;
        dfs(next);
    }
}

void chk_bin_matching()
{
    int edg;

    memset(bin_color, 0, sizeof(bin_color));
    edg = QMark.front();
    bin_color[edg] = w;
    isbin = true;
    dfs(edg);
}
*/

bool chk_bin_matching()
{
    int edg, next, color;

    memset(bin_color, 0, sizeof(bin_color));
    Q_bfs.clear();
    edg = QMark.front();
    Q_bfs.push_front(edg);
    bin_color[edg] = w;
    while (!Q_bfs.empty())
    {
        edg = Q_bfs.front();
        Q_bfs.pop_front();
        vector<int>::iterator end, begin;
        end = V[edg].end();
        color = bin_color[edg];
        for (begin = V[edg].begin() ; begin != end ; begin++)
        {
            next = *begin;
            if (!bit_set.test(next))
                continue;
            if (color == 0 - bin_color[next])
                continue;
            if (color == bin_color[next])
                return false;
            bin_color[next] = 0 - color;
            Q_bfs.push_back(next);
        }
    }
    return true;
}

void tarjan(int v_cur, int cities)
{
    int v_adj, add;
    DFN[v_cur] = LOW[v_cur] = ++Dindex;
    Q.push_front(v_cur);
    vector<int>::iterator iter_end, iter_begin;
    iter_end = V[v_cur].end();
    for (iter_begin = V[v_cur].begin() ; iter_begin != iter_end ; iter_begin++)
    {
        v_adj = *iter_begin;
        if (0 == DFN[v_adj])
        {
            tarjan(v_adj, cities);
            if (LOW[v_adj] < LOW[v_cur])
                LOW[v_cur] = LOW[v_adj];
            if (LOW[v_adj] >= DFN[v_cur])
            {
                Bcnt++;
                int edg, odd = add = 0;
                bit_set.reset();
                do
                {
                    edg = Q.front();
                    Q.pop_front();
                    bit_set.set(edg);
                    //Belong[edg] = Bcnt;

                    odd++;
                    QMark.push_back(edg);
                }while(edg != v_adj);
                odd++;
                //Belong[v_cur] = Bcnt;

                bit_set.set(v_cur);
                QMark.push_back(v_cur);

                isbin = false;
                if (odd % 2 == 0)
                    isbin = chk_bin_matching();
                if (!isbin)
                {
                    add = mark_used();
                    ret += add;
                }
                QMark.clear();
                /*debug
                int k;
                for (k=1 ; k<=cities ; k++)
                    printf("%d ", Belong[k]);
                printf("\n");
                */
            }
        }
        else if (DFN[v_adj] < LOW[v_cur])
        {
            LOW[v_cur] = DFN[v_adj];
        }
    }
}

void solve(int cities)
{
    int i;
    Bcnt = Dindex = ret = 0;
    for (i=1 ; i<=cities ; i++)
    {
        if (0 == DFN[i])
            tarjan(i, cities);
    }
}

int main(int argc, char *argv[])
{
    int T, N, M, i, ai, bi;
    cin >> T;
    while (T--)
    {
        cin >> N >> M;
        for (i=0 ; i<M ; i++)
        {
            scanf("%d %d", &ai, &bi);
            V[ai].push_back(bi);
            V[bi].push_back(ai);
        }
        memset(DFN, 0, sizeof(DFN));
        //memset(Belong, 0, sizeof(Belong));

        memset(LOW, 0, sizeof(LOW));
        memset(used, 0, sizeof(used));
        memset(bin_color, 0, sizeof(bin_color));
        solve(N);
        cout << ret << endl;
        clear(N);
    }
}