UVa 10178 : Count the Faces

問題リンク:http://uva.onlinejudge.org/external/101/10178.html

問題概要：
平面グラフが与えられる
平面グラフによってできる領域の数＋１を求めよ(国と海の数を求めよ)

解法：
平面グラフの国の数 s は辺の数をe,ノードの数をvとすると
s = e - v + 1　となる（オイラーの公式より）
ちなみにこれは埋蔵次元が２以下でなければならない
今回は平面グラフなので埋蔵次元は２以下となるため条件を満たす

なので e - v + 2 (海があるので+1) が答えとなるのだが、
今回はグラフが１つではなく複数存在する様なので
dfsで連結なノードの集合毎に国の数を数え、最後に+1して答えとする

気をつけるべき点
・グラフは複数存在する
・多重辺、自己ループが存在する

コーナーケース
Input :
2 0
2 3
A B
B A
A B
1 1
A A
6 6
A B
B C
C A
D E
E F
F D

Output :
1
3
2
3

コード：

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define MAX 1000000

using namespace std;

int V,E;
vector<int> G[MAX];

void dfs(vector<int> &group,bool *used,int cur)
{
  rep(i,G[cur].size())if(!used[G[cur][i]])
    {
      group.push_back(G[cur][i]);
      used[G[cur][i]] = true;
      dfs(group,used,G[cur][i]);
    }
}

int main()
{
  while(cin >> V >> E)
    {
      rep(i,V)G[i].clear();
      map<string,int> getIndex;
      int index = 0;
      rep(i,E)
	{
	  string a,b;
	  cin >> a >> b;
	  if(getIndex.find(a) == getIndex.end())getIndex[a] = index++;
	  if(getIndex.find(b) == getIndex.end())getIndex[b] = index++;
	  int aindex = getIndex[a], bindex = getIndex[b];
	  G[aindex].push_back(bindex);
	  G[bindex].push_back(aindex);
	}

      int ans = 0;
      bool used[index];
      rep(i,index)used[i] = false;
      rep(i,index)
	{
	  if(used[i])continue;
	  used[i] = true;
	  vector<int> group;
	  group.push_back(i);
	  dfs(group,used,i);
	  int v,e = 0;
	  v = group.size();
	  rep(j,group.size())e += G[group[j]].size();
	  e /= 2;
	  ans += e - v + 1;
	}
      cout << ans+1 << endl;
    }
  return 0;
}