【hihoCoder】1121：二分图一·二分图判定

  题目   http://hihocoder.com/problemset/problem/1121

无向图上有N个点，两两之间可以有连线，共有M条连线。

如果对所有点进行涂色（白/黑），判定是否存在一个合理的涂色方案，使得图上每一条连线两端的顶点颜色都不相同。

  思路  

1. 深度优先搜索：把图上所有的点都遍历一遍 

  代码注意点   

1. 因为不想用二维数组，采用vector<vector<int>>的类型。这时要注意初始化方式：

不该用的方式

//1. 初始化
vector<int> tmp(N); 
vector<vector<int>> data(N, tmp);
//2. 访问方式
cin>>data[i][j]

合适的方式

//1. 初始化
vector<vector<int>> data;
data.resize(N);
//2. 访问方式
int x, y;
cin>>x>>y;
data[x].push_back(y);
data[y].push_back(x);

2. vector的resize/reserve函数

1) void reserve (size_type n);

• 预分配存储区大小，即capacity，但是没有对内存初始化，不能有效地访问
• 实际分配的大小可能大于n，即capacity >= n

2) void resize (size_type n, value_type val = 0);

• 重新分配大小，vector中现有的元素个数 size()
• n <= 原始大小，则减少size()值，保存前n个元素
• n >= 原始大小，则插入元素（默认为0， 或设置的 val），使size()达到n
• n > capacity()，则重新分配存储空间 

 源码  

#include <iostream>
#include <vector>
using namespace std;

bool setPeople(vector<vector<int>>& date, vector<int>& people, int index)
{
    int num = date[index].size();
    for (int i = 0; i < num; i++)
    {
        int j = date[index][i];
        if (people[j] == 0)//还没有设置过
        {
            people[j] = -people[index];
            if (!setPeople(date, people, j))
                return false;
        }
        else  if (people[j] == people[index])//已经设置过, 不符合要求
            return false;
    }
    return true;
}
int main()
{
    int T, N, M, i;//N个人，M对
    cin >> T;
    vector<int> people;//0: 没有设置，1：红色 2：黑色
    vector<vector<int>> date;
    while (T-- > 0)
    {
        cin >> N >> M;
        people.clear();
        date.clear();
        people.resize(N + 1, 0);
        date.resize(N + 1);
        
        for (i = 0; i < M; i++)
        {
            int a, b;
            cin >> a >> b;
            date[a].push_back(b);
            date[b].push_back(a);
        }
        for (i = 1; i <= N; i++)
        {            
            if (people[i] == 0)//没有设置过
            {
                people[i] = -1;
                if (!setPeople(date, people, i))//有出现错误
                    break;
            }
        }
        if (i != N + 1)
            cout << "Wrong" << endl;
        else
            cout << "Correct" << endl;
    }
    return 0;
}