解題區►解題區 - UVa

UVa 1086 - The Ministers' Major Mess

Problem

有 M 個人，B 個方案要進行投票表決。

每個人可以選擇 ki 個方案進行通過或不通過，其中 ki <= 4。找到一種方案的通過方式滿足所有人選擇項目的一半以上 (不含)。

Sample Input

1
2
3
4
5
6
7
5 2 
4 2 y 5 n 3 n 4 n
4 4 y 3 y 5 n 2 y 
4 2 
4 1 y 2 y 3 y 4 y 
3 1 n 2 n 3 n 
0 0

Sample Output

1
2
Case 1: ?y??n 
Case 2: impossible

Solution

由於 ki <= 4，又要滿足一半以上。則對於 ki = 1, 2 需要全部符合他們的項目。對於 ki = 3, 4 則不滿足其中一個選項 i 時，其他的選項 j 都必須滿足。

藉此套用 2-sat 模型，找到是否可能有可行解。當要輸出 2-sat 其中一解時，窮舉每一個變數為 true / false，建立一條邊 x -> x' / x' -> x，再用 2-sat 模型判斷是否有解即可。

找解速度會慢很多，這樣會比較好撰寫。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
// 2-satisify problem
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAXN = 262144;
class TwoSat {
public:
	int n;
	vector<int> g[MAXN];
	// <SCC begin>
	int vfind[MAXN], findIdx;
	int stk[MAXN], stkIdx;
	int in_stk[MAXN], visited[MAXN];
	int contract[MAXN];
	int scc_cnt;
	// <SCC end>
	int scc(int u) {
	    in_stk[u] = visited[u] = 1;
	    stk[++stkIdx] = u, vfind[u] = ++findIdx;
	    int mn = vfind[u], v;
	    for(int i = 0; i < g[u].size(); i++) {
	    	v = g[u][i];
	        if(!visited[v])
	            mn = min(mn, scc(v));
	        if(in_stk[v])
	            mn = min(mn, vfind[v]);
	    }
	    if(mn == vfind[u]) {
	        do {
	            in_stk[stk[stkIdx]] = 0;
	            contract[stk[stkIdx]] = u;
	        } while(stk[stkIdx--] != u);
	        scc_cnt++;
	    }
	    return mn;
	}
	void addEdge(int u, int v) { // u -> v
		g[u].push_back(v);
	}
	int solvable() {
		for (int i = 0; i < n; i++)
			visited[i] = in_stk[i] = 0;
        scc_cnt = 1;
        for (int i = 0; i < n; i++) {
        	if (visited[i])	continue;
        	stkIdx = findIdx = 0;
        	scc(i);
        }
        
        for(int i = 0; i < n; i += 2)
			if(contract[i] == contract[i^1])
				return 0;
		return 1;
	}
	void computeChoice() {
		if (!solvable())
			return ;
		for (int i = 0; i < n; i += 2) {
			int val = 0;
			g[i].push_back(i^1);
			if (solvable())	val |= 1;
			g[i].pop_back();
			
			g[i^1].push_back(i);
			if (solvable())	val |= 2;
			g[i^1].pop_back();
			
			printf("%c", "-yn?"[val]);
		}
		puts("");
	}
	void init(int n) {
		this->n = n;
		for (int i = 0; i < n; i++)
			g[i].clear();
	}
} g;
// more than half of his or her opinions satisfied
// opinion <= 4
int main() {
	int n, m, cases = 0;
	char s[128];
	while (scanf("%d %d", &n, &m) == 2 && n) {
		g.init(2 * n);
		
		for (int i = 0; i < m; i++) {
			int vote[8], k, x;
			scanf("%d", &k);
			for (int j = 0; j < k; j++) {
				scanf("%d %s", &x, s);
				x--;
				vote[j] = x * 2 + (s[0] == 'y');
			}
			if (k <= 2) { // all satisfied
				for (int p = 0; p < k; p++)
					g.addEdge(vote[p]^1, vote[p]);
			} else { // one fail
				for (int p = 0; p < k; p++) {
					for (int q = 0; q < k; q++) {
						if (p == q)	continue;
						// p-th opinion fail
						g.addEdge(vote[p]^1, vote[q]);
					}
				}
			}
		}
		
		printf("Case %d: ", ++cases);
		if (!g.solvable()) {
			puts("impossible");
		} else {
			g.computeChoice();
		}
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 11119 - Chemical Attraction

Problem

給予由陰陽離子構成的化合物，混和後會根據活性表發生變化，求其中一種穩定態。

所謂的穩定態，就是不會兩個化合物之間可以進行陰陽離子的互換。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
3
Ba Sr Th
3
Cl Br Fl
1 2 3
1 3 2
2 1 3
2 1 3
1 3 2
1 2 3
3
BaFl SrBr ThCl
5
BaFl BaFl SrFl SrCl ThFl
0
3
Na Ag Fe
5
Su Zi Xe Ar Do
1 2 4 3 5
5 3 1 2 4
2 3 1 4 5
3 2 1
3 2 1
1 3 2
1 2 3
2 1 3
10
NaDo AgDo AgAr FeXe NaXe
AgZi AgZi NaSu AgSu FeDo
0
0

Sample Output

1
2
3
4
5
6
7
8
Scenario 1, Mixture 1:
BaCl SrBr ThFl
Scenario 1, Mixture 2:
BaFl BaCl SrFl SrFl ThFl
Scenario 2, Mixture 1:
NaDo AgSu AgSu FeDo NaXe AgZi AgZi NaXe AgAr FeDo

Solution

一個經典的穩定婚姻問題 (stable marriage problem)，可以用 Gale-Shapley algorithm 解決匹配兩邊個數相同的穩定婚姻。穩定婚姻有兩組最優解，其中一組最優解於男方、另外一組為女方，其最優解即為候選的排序為字典順序最小的。

假設現在要給男方一個最優解，那麼根據貪心的思路，男方要不斷地按照排名清單去向女方求婚，如果女方心中對求婚男方的排名更好，則男方求婚成功，而前男友就會被拋棄，被拋棄的男方將會根據清單再找下去。做法類似增廣路徑。

為什麼這樣能趨近穩定呢？原因是這樣子的，由於男方不斷地求婚，女方配對男方的排名會越來越好，男方被拋棄後，求婚對象則會越來越差。

假定男方為 A, B，女方為 1, 2，優先順序為括弧內，越靠前表示順位越高。

1
2
A(1, 2) - 1(B, A)
B(1, 2) - 2(A, B)

假如 A - 1 和 B - 2，則女 1 更喜歡男 A，女 2 更喜歡男 B，男方中也更喜歡對方的配偶 (這個例子中是相同)，而造成配對交換，這即為不穩定婚姻。

解決會交換的情況。當嘗試配對一對男女時，如何保證不會發生循環交換？當男主被某女拋棄，則表示某女心中有一個更好的某男。男方按照順序求婚，就不會發生男方中會更喜歡對方的配偶而交換。

單看女方，了解到拋棄的動作是有限的，算法就能在 O(N^2) 解決。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// Gale-Shapley algorithm, stable marriage problem
#include <stdio.h>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 256;
class GaleShapley { // produce the best possible choice for the mans
public:
    int mOrder[MAXN][MAXN], fOrder[MAXN][MAXN];
    int fPref[MAXN][MAXN];
    int man[MAXN], woman[MAXN];
    int N;
    void init(int n) {
        N = n;
    }
    void stable() {
        int mIdx[MAXN];
        for (int i = 0; i < N; i++)
            man[i] = woman[i] = -1, mIdx[i] = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                fPref[i][fOrder[i][j]] = j;
        }
        for (int i = 0; i < N; i++) {
            int m = i, w;
            while (m >= 0) {
                w = mOrder[m][mIdx[m]++];
                while (m >= 0 && (woman[w] == -1 || fPref[w][woman[w]] > fPref[w][m])) {
                    man[m] = w;
                    swap(m, woman[w]);
                }
            }
        }
    }
} g;
char s[MAXN];
int tA[MAXN][MAXN], tB[MAXN][MAXN], rtA[MAXN][MAXN], rtB[MAXN][MAXN];
int main() {
    int N, M, x, n;
    int cases = 0;
    while (scanf("%d", &N) == 1 && N) {
    	map<string, int> Rn, Rm;
        for (int i = 0; i < N; i++)
        	scanf("%s", s), Rn[s] = i;
        scanf("%d", &M);
        for (int i = 0; i < M; i++)
        	scanf("%s", s), Rm[s] = i;
    	
    	for (int i = 0; i < N; i++)
    		for (int j = 0; j < M; j++)
    			scanf("%d", &tA[i][j]), tA[i][j]--, rtA[i][tA[i][j]] = j;
    	for (int i = 0; i < M; i++)
    		for (int j = 0; j < N; j++)
    			scanf("%d", &tB[i][j]), tB[i][j]--, rtB[i][tB[i][j]] = j;
    	++cases;
    	int tcases = 0;
    	while (scanf("%d", &n) == 1 && n) {
    		vector<string> A, B;
    		for (int i = 0; i < n; i++) {
    			scanf("%s", s);
    			string a(2, 'a'), b(2, 'a');
    			a[0] = s[0], a[1] = s[1];
    			b[0] = s[2], b[1] = s[3];
    			A.push_back(a), B.push_back(b);
    		}
    		g.init(n);
    		
    		for (int i = 0; i < n; i++) {
    			vector< pair<int, int> > p;
    			int u = Rn[A[i]], v;
    			for (int j = 0; j < n; j++) {
    				v = Rm[B[j]];
    				p.push_back(pair<int, int>(tA[u][v], j));
    			}
    			sort(p.begin(), p.end(), greater< pair<int, int> >());
    			for (int j = 0; j < n; j++) {
    				g.mOrder[i][j] = p[j].second;
//    				printf("%d ", p[j].second);
    			}
//    			puts(" -m");
    		}
    		
    		for (int i = 0; i < n; i++) {
    			vector< pair<int, int> > p;
    			int u = Rm[B[i]], v;
    			for (int j = 0; j < n; j++) {
    				v = Rn[A[j]];
    				p.push_back(pair<int, int>(tB[u][v], j));
    			}
    			sort(p.begin(), p.end(), greater< pair<int, int> >());
    			for (int j = 0; j < n; j++) {
    				g.fOrder[i][j] = p[j].second;
//    				printf("%d ", p[j].second);
    			}
//    			puts(" -f");
    		}
    		
    		g.stable();
    		
    		printf("Scenario %d, Mixture %d:\n", cases, ++tcases);
    		for (int i = 0; i < n; i++) {
    			int m = g.man[i];
    			if (i)	printf(" ");
    			printf("%s%s", A[i].c_str(), B[m].c_str());
    		}
    		puts("\n");
    	}
    }
    return 0;
}
/*
 */
Read More +
學校課程►資訊安全

區段加密筆記

本篇筆記，僅為個人淺見

什麼是區段加密

先了解 stream ciphers 和 block ciphers 的差異

  • stream ciphers 特別在於加密用的 key 不斷地變更，並且以極少數的情況下重複使用，每一次加密針對一個 byte 或者是 bit 進行加密。加解密的兩方，可以同時產生出相同 random key。

  • block ciphers 只用同一份 key，把加密文件一次用一個 block 文字進行加密，利用換位 (位置交換)、替換 (文字替換) … 等方式，讓相似內容的明文，可以產出差異極大的密文 (訊息獨立)。

從概念上，串流加密是絕對安全，如果雙方有辦法在不通訊下，可以產生出 random key，而且不重複使用 key，攻擊者會無從下手。但是現今很多 random 的產生方法仍然是演算法的數學模型，因此一定有規則。

而區段加密的好處，在於換位、替換、 … 等方式，將密文的相似度降低，即使明文長得很相似，攻擊者無法誘導相似明文的傳遞，導致 key 快速被發現，因為密文的差異性導致規則難以被破解。

加密設計基礎原則

  • confusion 困惑
    密文跟 key 的關係盡可能混亂，根據加密的方式，有可能某些 key 會造成特殊的密文規則，這種弱 key 要不不存在、要不不使用。減少攻擊者對密文的觀察，就可以找到 key。

  • diffusion 散播
    當明文相當相似時，也許只有幾個 bit 不同，產生出來的密文的差異性也要相當高，否則攻擊者可以推導加密原理，藉由 bitwise 將密文修改，讓解密者受到誤導。

Data Encryption Standard (DES)

  • 每一次加密 64 -bit 的資料，用 56 -bit 的 key。
    這是一個很詭異的現象，通常 key 的長度會比 data 的長度來得大。
  • 經過 16 回合的加密，並且每一個回合用 56 -bit 的 key 產生出 48 -bit 的 subkey 針對 64 -bit 的資料加密。
  • 加密過程會有擴充 subkey 和選擇一部分的 subkey，並且拿一部分的明文對 subkey 加密。

將明文對切成兩個部分，一部分加密 subkey，另一部分根據加密過的 subkey 進行加密。在下一個回合，交換部分明文和部分密文的位置，讓所有的明文都進入到混亂狀態。

在解密時，知道 subkey 的產生規則，然後拿部分明文，加密 subkey 後，得到部分密文的加密要件，逆推回去。這一個繁複的過程，主要是製造 confusion，而 diffusion 的部分，則是在擴充 key 和拿部分明文加密 subkey 時，發生雪崩效應，因為拿部分明文進行加密 subkey，會造成 key 差異性放大。

儘管明文相似程度很高，卻會因為處理過程將差異轉移到 subkey 很多的位置的不同，經過輪替加密。無法利用頻率的方式，找到明文差異會造成密文的哪一個部分的差異。

正確性

為什麼 DES 可以被正確解密？概念上，一個密文只能對應一個明文，這樣才符合正確解密的定義。因此不同的明文，也要產生出來不同的密文。

證明從輪替下手，部分明文 A 會保留到下一個輪替，而部分明文 A 會加密部分明文 B，假設兩個明文在 A 部分不同，則在密文部分就會不同 (因為保留)，假設是 B 部分不同，加密 (XOR 加密) 後也會不同。數學歸納法得證。

加密強度分析

因為 subkey 產生方式和換位、替換的規格是明定，與 key 無關。因此 key 長短將影響加密的強度，從現在分析 56 -bit 在數個小時內就會被解出來。

為什麼 subkey 產生方式和換位、替換的規格是明定？
因為雪崩效應的造成需要某些放大效果，因此表格要符合某些設計規則。

攻擊方法

  • Timing Attacks 加密時間攻擊，因為電腦運算的速度受輸入要件影響，如果 bit 變換數大，會導致加密時間拉長，藉以分析明文。

  • Power Attacks 偵測能源消耗，因為運算所需要的能量不同，隨著時間能到得到能源使用圖，就能分析加密過程的情況。也有為了防止這種偵測，考慮將所有運算做得一樣耗電，這有可能本末倒置。

  • Analytic Attacks 分析攻擊，從統計學的角度進行攻擊，從密文差異下手、從已知密文、明文解方程式、key 與加密結果的關聯性 … 等。

Block mode

ECB

Electronic CodeBook (ECB)，不變的 key，需要加密器和解密器，加解密的複雜度可能不同。

  • 優點：
    構造簡單、容易實做
  • 缺點：
    長時間下，容易被偵測。影像資料的差異性不大，很容易被辨識到重複性，相較於文字很容易受前後文的影響。

CBC

Cipher Block Chaining (CBC)，不變的 key，以及前一個密文會先針對明文加密。

  • 優點：
    相同明文，會因為前一個的密文不同造就出不同的密文，也就是加密器多一個新的狀態。
  • 缺點：
    • 一個密文 Ci 的錯誤，會導致兩個明文解析錯誤 (Pi & Pi+1)。
    • 第一次加密很容易被抽換 bitwise，因為每次驅動的 Initial Vector 都相同。

CFB

Cipher FeedBack (CFB)，類似 CBC，但前一個密文的結果只影響一部分的加密關係，然後將前一段密文狀態加密 key，再對明文加密。

  • 優點：
    • 支持即時 (real-time) 通訊
    • 只需要加密器，加密做兩次相當於解密。
    • 支持自同步 (self-synchronization)，即使中斷連線、訊息錯誤，可以在數個週期後再次同步運作。
    • 藉由自同步的概念，可以捨棄掉 Initial Vector。
    • 後半部的明文，可以透過週期性的部分密文建立解密狀態，支持 random access。
  • 缺點：
    • error propagation 錯誤增長，當一個訊息錯誤時，需要好幾個週期後才能修正回來，這導致中間的解密訊息都不能用。
    • 雜訊過多的情況下，不宜使用。

OFB

Output FeedBack (OFB)，類似於 CFB，將前一段的加密 key 拿回來加密，不依賴接收的密文狀態。

  • 優點：
    • 支持即時 (real-time) 通訊
    • 只需要加密器，加密做兩次相當於解密。
    • 相較於 CFB，沒有錯誤增長的情況。
    • 依序使用的 key，可以事先算出來，然後依次使用。
    • 雜訊下支持的能力好。
  • 缺點：
    • 必須一直保持同步
    • 訊息被修改時，不易被發現，只單純影響單一明文 (沒有錯誤增長)。
    • 起始狀態的 Initial Vector，不能重複使用，否則很容易被攻擊者抓到。
    • 加設沒有預先算 key，沒辦法解密出後半部的明文。

CTR

Counter (CTR)，類似於 OFB，直接利用計數器作為加密 key。

  • 優點：
    • 加解密可以平行化處理，如果加解密速度耗時，可以選擇這一種。
    • 支持 random access。
  • 缺點：
    • 必須一直保持同步
    • 訊息被修改時，不易被發現，只單純影響單一明文 (沒有錯誤增長)。
    • 起始狀態的 Initial Vector，不能重複使用，否則很容易被攻擊者抓到。
Read More +
解題區►解題區 - UVa

UVa 1013 - Island Hopping

Problem

島嶼居民要建造網路連到本島，假設現在島嶼跟島嶼之間都沒有架設網路線，現在開始建造網路，使得每一個島嶼都可以與本島或者是間接相連。

請問平均等待時間需要多少。

所有的路線，在同一時刻開始建造，以每一天一公里的速度建造所有的邊，而每一條邊都以歐幾里得距離為路線長度。

Sample Input

1
2
3
4
5
6
7
8
9
7
11 12 2500
14 17 1500
9 9 750
7 15 600
19 16 500
8 18 400
15 21 250
0

Sample Output

1
Island Group: 1 Average 3.20

Solution

一開始沒有注意到同時建造，發現這條規則後，將所有邊的長度由小到大排序，使用并查集去紀錄，找到第一個時刻連到本島的時間。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h> 
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 64;
double X[MAXN], Y[MAXN], M[MAXN];
struct Edge {
	int x, y;
	double v;
	Edge(int a = 0, int b = 0, double c = 0):
		x(a), y(b), v(c) {}
	bool operator<(const Edge &x) const {
		return v < x.v;
	}
};
vector<Edge> E;
int parent[MAXN], weight[MAXN];
double weight2[MAXN];
int findp(int x) {
	return parent[x] == x ? x : parent[x] = findp(parent[x]);
}
int joint(int x, int y) {
	x = findp(x), y = findp(y);
	if (x == y)	
		return 0;
	if (weight[x] > weight[y]) {
		parent[y] = x, weight[x] += weight[y];
		weight2[x] += weight2[y];
	} else {
		parent[x] = y, weight[y] += weight[x];
		weight2[y] += weight2[x];
	}
	return 1;
}
double solve(int n) {
	sort(E.begin(), E.end());
	double div = 0, sum = 0;
	int u, v;
	for (int i = 0; i < n; i++)
		parent[i] = i, weight[i] = 1, weight2[i] = M[i], div += M[i];
		
	for (int i = 0; i < E.size(); i++) {
		u = E[i].x, v = E[i].y;
		if (findp(u) != findp(v)) {
			if (findp(u) == findp(0))
				sum += weight2[findp(v)] * E[i].v;
			if (findp(v) == findp(0))
				sum += weight2[findp(u)] * E[i].v;
			joint(u, v);
		}
	}
	return sum / div;
}
int main() {
	int n, cases = 0;
	while (scanf("%d", &n) == 1 && n) {
		for (int i = 0; i < n; i++)
			scanf("%lf %lf %lf", &X[i], &Y[i], &M[i]);
		E.clear();
		for (int i = 0; i < n; i++) {
			for (int j = i+1; j < n; j++) {
				double v = hypot(X[i] - X[j], Y[i] - Y[j]);
				E.push_back(Edge(i, j, v));
			}
		}
		
		double ret = solve(n);
		
		printf("Island Group: %d Average %.2lf\n", ++cases, ret);
		
		puts("");
	}
	return 0;
}
/*
7
11 12 2500
14 17 1500
9 9 750
7 15 600
19 16 500
8 18 400
15 21 250
0
*/
Read More +
解題區►解題區 - UVa

UVa 1186 - Chat Rooms

Problem

聊天室會過濾過機器人般的垃圾留言，規則如下

  • 使用的單詞，出現連續子音的個數大於 5 個
  • 使用者最後送出的 10 個訊息中，有 2 行連續子音的個數大於 4 個，並且當前行也存在連續子音的個數大於 4 個。
  • 使用者最後送出的 10 個訊息中，與當前訊息相同的行數大於 1 個。

只要符合其中一條，訊息將無法發送，但是系統仍然會記錄下你曾經發送過的訊息，其他使用者無法看到被過濾的訊息。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
12
hello
how r u?
where r u from?
kjhh kh kgkjhg jhg
where r u from?
i am from London, Ontario, Canada
how r you nxw?
now
where r u from?
kjhh kh kgkjhg jhg
very good
it is very cold here.

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
y
y
y
n
y
y
y
y
n
n
y
y

Solution

這題算簡單，但是題目描述過於鬼畜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h> 
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <ctype.h>
using namespace std;
vector<string> toToken(string s) {
	stringstream sin(s);
	string token;
	vector<string> r;
	while (sin >> token)
		r.push_back(token);
	return r;
}
int isConsonant(char c) {
	c = tolower(c);
	if (c == 'a')	return 0;
	if (c == 'e')	return 0;
	if (c == 'i')	return 0;
	if (c == 'o')	return 0;
	if (c == 'u')	return 0;
	if (c == 'y')	return 0;
	return 1;
} 
int checkCond1(vector<string> &t) {
	for (int i = 0; i < t.size(); i++) {
		int c = 0;
		for (int j = 0; j < t[i].length(); j++) {
			if (isConsonant(t[i][j]))
				c++;
			else
				c = 0;
			if (c > 5)	return 0;
		}
	}
	return 1;
}
int checkCond2(vector<string> &t, vector<int> &D2) {
	int A = 0, B = 0;
	for (int i = 0; i < t.size(); i++) {
		int c = 0;
		for (int j = 0; j < t[i].length(); j++) {
			if (isConsonant(t[i][j]))
				c++;
			else
				c = 0;
			if (c > 4)	A = 1;
		}
	}
	for (int i = D2.size() - 1; i >= max(0, (int) D2.size() - 10); i--) {
		if (D2[i] > 0)
			B++;
	}
	return !(A && B > 2);
}
int checkCond3(string s, vector<string> &D3) {
	int A = 0;
	for (int i = D3.size() - 1; i >= max(0, (int) D3.size() - 10); i--) {
		if (D3[i] == s)
			A++;
		if (A > 1)
			return 0;
	}
	return 1;
}
int count4(vector<string> &t) {
	int A = 0;
	for (int i = 0; i < t.size(); i++) {
		int c = 0;
		for (int j = 0; j < t[i].length(); j++) {
			if (isConsonant(t[i][j]))
				c++;
			else
				c = 0;
			if (c > 4)	A = 1;
		}
	}
	return A;
}
int main() {
	int n;
	char s[256];
	while (scanf("%d", &n) == 1) {
		while (getchar() != '\n');
		vector< vector<string> > D;
		vector<int> D2;
		vector<string> D3;
		for (int i = 0; i < n; i++) { 
			gets(s);
			vector<string> t = toToken(s);
			int ok = 1;
			if (!checkCond1(t))
				ok = 0;
			else if (!checkCond2(t, D2))
				ok = 0;
			else if (!checkCond3(s, D3)) 
				ok = 0;
			D.push_back(t), D2.push_back(count4(t)), D3.push_back(s);
			puts(ok ? "y" : "n");
		} 
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 1462 - Fuzzy Google Suggest

Problem

模擬 Google 的模糊搜尋，使用編輯距離找到相符的前綴單詞數量。

編輯距離的限制小於等於 2。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
4 
content 
common 
onganize 
case 
7 
c 0 
con 0 
con 2 
con 1 
com 1
comm 2 
cog 1

Sample Output

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

Solution

對於每一個詢問，沒辦法把每一個單字都拿出來嘗試過一次。

建造一個 trie，然後在 trie 上面進行編輯距離的 dp 規則，當搜尋到重覆的結果時，可以立刻返回，由於編輯距離小於等於 2，重複走訪的可能性低很多，因此用一個懶標記，如果前綴已經符合，則下次走訪就沒有必要搜索下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#define MAXCHAR 26
#define MAXS (1024)
#define MAXNODE (1048576<<2)
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
class Trie {
public:
    struct Node {
        Node *next[MAXCHAR];
        int cnt, label;
        void init() {
            cnt = label = 0;
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size, cases;
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = cases = 0;
        root = getNode();
    }
    inline int toIndex(char c) {
        return c - 'a';
    }
    // merge trie
    void merge_dfs(Node *p, Node *q) {
        for (int i = 0; i < MAXCHAR; i++) {
            if (q->next[i]) {
                Node *u = p->next[i], *v = q->next[i];
                if (u == NULL)
                    p->next[i] = getNode(), u = p->next[i];
                u->cnt += v->cnt;
                merge_dfs(u, v);
            }
        }
    }
    void merge(const Trie &other) {
        merge_dfs(root, other.root);
    }
    // basis operation
    void insert(const char str[], int w) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        	p->cnt += w;
        }
    }
    int find(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        return p->cnt;
    }
    // fuzzy find
    void fuzzy_dfs(Node *u, int idx, const char s[], int fuzzy_edit) {
    	if (fuzzy_edit < 0)			return ;
		if (u->label == cases + 1)	return ;
    	if (s[idx] == '\0') {
    		u->label = cases + 1;
    		return ;
		}
			
		if (u->label < cases)
			u->label = cases;
        for (int i = 0; i < MAXCHAR; i++) {
            if (u->next[i]) {
                if (toIndex(s[idx]) == i)
                	fuzzy_dfs(u->next[i], idx+1, s, fuzzy_edit);
                else
                	fuzzy_dfs(u->next[i], idx+1, s, fuzzy_edit-1); // replace s[idx]
                fuzzy_dfs(u->next[i], idx, s, fuzzy_edit-1); // insert s[idx]
            }
        }
		fuzzy_dfs(u, idx+1, s, fuzzy_edit-1); // delete s[idx]
    }
    int fuzzy_count(Node *u) {
    	if (u->label == cases+1)
    		return u->cnt;
    	if (u->label < cases)
    		return 0;
		int ret = 0;
        for (int i = 0; i < MAXCHAR; i++) {
            if (u->next[i])
                ret += fuzzy_count(u->next[i]);
        }
        return ret;
    }
    int fuzzyFind(const char str[], int fuzzy_edit) {
    	cases += 2;
    	fuzzy_dfs(root, 0, str, fuzzy_edit);
    	return fuzzy_count(root);
    }
    
    void free() {
        return ;
        // owner memory pool version
        queue<Node*> Q;
        Q.push(root);
        Node *u;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] != NULL) {
                    Q.push(u->next[i]);
                }
            }
            delete u;
        }
    }
} tool;
char s[MAXS];
int main() {
    int N, Q, f;
    while (scanf("%d", &N) == 1 && N) {
    	tool.init();
    	while (getchar() != '\n');
    	
    	for (int i = 0; i < N; i++) {
    		gets(s);
    		tool.insert(s, 1);
    	}
    	scanf("%d", &Q);
    	for (int i = 0; i < Q; i++) {
    		scanf("%s %d", s, &f);
    		int ret = tool.fuzzyFind(s, f);
    		printf("%d\n", ret);
    	}
    	
    	tool.free();
    }
    return 0;
}
/*
4 
content 
common 
onganize 
case 
7 
c 0 
con 0 
con 2 
con 1 
com 1
comm 2 
cog 1
 */
Read More +
解題區►解題區 - UVa

UVa 1113 - Multiple Morse Matches

Problem

給摩斯電碼的編碼方式，以及一串沒有切割的主字串，和可能使用的單字集，請問有多少不同的解析方式。

Sample Input

1
2
3
4
5
6
7
8
9
10
1
.---.--.-.-.-.---...-.---.
6
AT
TACK
TICK
ATTACK
DAWN
DUSK

Sample Output

1
2

Solution

這題很明顯地是一道 O(nm) 的動態規劃，dp[i] 表示長度為 i 的解析方法數，藉由 match S[i, j] 轉移成 dp[j] += dp[i]。

為了加速 match 的速度，先將字典集轉換成摩斯電碼，插入到 trie 中，當要做 match 時，相當於在 trie 走訪，可以高效地降低 O(m) 的嘗試。變成 O(nn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <map>
#define MAXCHAR 2 
#define MAXS (4096)
#define MAXNODE (1048576<<2)
#pragma comment( linker, "/STACK:1024000000,1024000000")
using namespace std;
class Trie {
public:
    struct Node {
        Node *next[MAXCHAR];
        int cnt;
        void init() {
            cnt = 0;
            memset(next, 0, sizeof(next));
        }
    } nodes[MAXNODE];
    Node *root;
    int size, cases;
    Node* getNode() {
        Node *p = &nodes[size++];
        p->init();
        return p;
    }
    void init() {
        size = cases = 0;
        root = getNode();
    }
    inline int toIndex(char c) {
        return c == '.';
    }
    // merge trie
    void merge_dfs(Node *p, Node *q) {
        for (int i = 0; i < MAXCHAR; i++) {
            if (q->next[i]) {
                Node *u = p->next[i], *v = q->next[i];
                if (u == NULL)
                    p->next[i] = getNode(), u = p->next[i];
                u->cnt += v->cnt;
                merge_dfs(u, v);
            }
        }
    }
    void merge(const Trie &other) {
        merge_dfs(root, other.root);
    }
    // basis operation
    void insert(const char str[], int w) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        p->cnt += w;
    }
    int find(const char str[]) {
        Node *p = root;
        for (int i = 0, idx; str[i]; i++) {
            idx = toIndex(str[i]);
            if (p->next[idx] == NULL)
                p->next[idx] = getNode();
            p = p->next[idx];
        }
        return p->cnt;
    }
        
    void free() {
        return ;
        // owner memory pool version
        queue<Node*> Q;
        Q.push(root);
        Node *u;
        while (!Q.empty()) {
            u = Q.front(), Q.pop();
            for (int i = 0; i < MAXCHAR; i++) {
                if (u->next[i] != NULL) {
                    Q.push(u->next[i]);
                }
            }
            delete u;
        }
    }
} tool;
char S[MAXS], T[MAXS], buf[MAXS];
string morse[] = {
	".-", "-...", "-.-.", "-..",
	".", "..-.", "--.", "....",
	"..", ".---", "-.-", ".-..",
	"--", "-.", "---", ".--.",
	"--.-", ".-.", "...", "-",
	"..-", "...-", ".--", "-..-",
	"-.--", "--.."};
int main() {
    int testcase, n;
    scanf("%d", &testcase);
    while (testcase--) {
    	tool.init();
    	
    	scanf("%s", S);
    	scanf("%d", &n);    	
    	for (int i = 0; i < n; i++) {
    		scanf("%s", T);
    		int m = 0;
    		for (int j = 0; T[j]; j++)
    			for (int k = 0; morse[T[j] - 'A'][k]; k++)
					buf[m++] = morse[T[j] - 'A'][k];
			buf[m] = '\0';
			tool.insert(buf, 1);
    	}
    	
    	int len = (int) strlen(S);
    	int dp[MAXS] = {};
    	dp[0] = 1;
    	for (int i = 0; i < len; i++) {
    		Trie::Node *p = tool.root;
    		for (int j = i; j < len; j++) {
    			int u = tool.toIndex(S[j]);
    			if (p->next[u] == NULL)
					break;
				p = p->next[u];
				dp[j+1] += dp[i] * p->cnt;
    		}
    	}
    	
    	printf("%d\n", dp[len]);	
    	if (testcase)
    		puts("");
		
		tool.free();    
    }
    return 0;
}
/*
 */
Read More +
解題區►解題區 - UVa

UVa 1352 - Colored Cubes

Problem

給予最多 4 個骰子，修改最少的面，使得每個骰子同構。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
3 
scarlet green blue yellow magenta cyan 
blue pink green magenta cyan lemon 
purple red blue yellow cyan green 
2 
red green blue yellow magenta cyan 
cyan green blue yellow magenta red 
2 
red green gray gray magenta cyan 
cyan green gray gray magenta red 
2 
red green blue yellow magenta cyan 
magenta red blue yellow cyan green 
3 
red green blue yellow magenta cyan 
cyan green blue yellow magenta red 
magenta red blue yellow cyan green 
3 
blue green green green green blue 
green blue blue green green green 
green green green green green sea-green 
3 
red yellow red yellow red yellow 
red red yellow yellow red yellow 
red red red red red red 
4 
violet violet salmon salmon salmon salmon 
violet salmon salmon salmon salmon violet 
violet violet salmon salmon violet violet 
violet violet violet violet salmon salmon 
1 
red green blue yellow magenta cyan 
4 
magenta pink red scarlet vermilion wine-red 
aquamarine blue cyan indigo sky-blue turquoise-blue 
blond cream chrome-yellow lemon olive yellow 
chrome-green emerald-green green olive vilidian sky-blue 
0

Sample Output

1
2
3
4
5
6
7
8
9
10
4 
2 
0 
0 
2 
3 
4 
4 
0 
16

Solution

由於每個骰子有 24 種同構排列，複雜度 O(24^4)。

將排列對齊後，使用貪心算法，將每一個 column 找到最多相同元素，剩餘的就是最少修改元素。

類似漢明距離的最少修改。順便將之前的代碼重新構造。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
struct DICE {
    int dice[6]; // front, right, up, back, left, down
	void rightTurn() {
    	static int t;
    	t = dice[0], dice[0] = dice[4];
    	dice[4] = dice[3], dice[3] = dice[1], dice[1] = t;
	}
	void upTurn() {
    	static int t;
    	t = dice[0], dice[0] = dice[5];
    	dice[5] = dice[3], dice[3] = dice[2], dice[2] = t;
	}
	void clockwise() {
	    static int t;
	    t = dice[2], dice[2] = dice[4];
	    dice[4] = dice[5], dice[5] = dice[1], dice[1] = t;
	}
	void print() {
		for (int i = 0; i < 6; i++)
			printf("%d ", dice[i]);
		puts("");
	}
	vector<DICE> generate() {
		vector<DICE> ret;
		DICE tmp = *this;
		
	    for (int i = 0; i < 4; i++) {
	        for(int j = 0; j < 4; j++) {
	        	ret.push_back(tmp);
	            tmp.clockwise();
	        }        
	        tmp.rightTurn();
	    }
	    tmp.upTurn();
	    for (int i = 0; i < 2; i++) {
	        for (int j = 0; j < 4; j++) {
	            ret.push_back(tmp);
	            tmp.clockwise();
	        }        
	        tmp.upTurn(), tmp.upTurn();
	    }
	    return ret;
	}
	bool operator<(const DICE &x) const {
		for (int i = 0; i < 6; i++)
			if (dice[i] != x.dice[i])
				return dice[i] < x.dice[i];
		return false;
	}
	bool operator==(const DICE &x) const {
		for (int i = 0; i < 6; i++)
			if (dice[i] != x.dice[i])
				return false;
		return true;
	}
};
int path[8];
vector<DICE> kind[8];
vector<DICE> permutation;
int ret = 0x3f3f3f3f, N;
int counter[32];
void dfs(int idx) {
	if (idx == N) {
		int ch = 0;
		for (int i = 0; i < 6; i++) {
			int mx = 0;
			memset(counter, 0, sizeof(counter));
			for (int j = 0; j < N; j++)
				mx = max(mx, ++counter[kind[j][path[j]].dice[i]]);
			ch += N - mx;
			if (ch >= ret)	return ;
		}
		ret = min(ret, ch); 
		return ;
	}
	for (int i = 0; i < kind[idx].size(); i++) {
		path[idx] = i;
		dfs(idx+1);
	}
}
int main() {
    DICE p;
    for (int i = 0; i < 6; i++)
    	p.dice[i] = i;
    permutation = p.generate();
    
    char s[128];
    while (scanf("%d", &N) == 1 && N) {
    	map<string, int> colors;
    	for (int i = 0; i < N; i++) {
    		int v[6];
    		for (int j = 0; j < 6; j++) {
    			scanf("%s", s);
    			int &x = colors[s];
    			if (x == 0)	x = colors.size();
    			v[j] = x;
    		}
    		DICE D;
    		D.dice[0] = v[0], D.dice[1] = v[1], D.dice[2] = v[2];
    		D.dice[5] = v[3], D.dice[4] = v[4], D.dice[3] = v[5];
    		
    		kind[i] = D.generate();
    		sort(kind[i].begin(), kind[i].end());
    		kind[i].resize(unique(kind[i].begin(), kind[i].end()) - kind[i].begin());
//    		printf("%d\n", kind[i].size());
    	}
    	
    	ret = 0x3f3f3f3f;
    	dfs(0);
    	printf("%d\n", ret);
    }
    return 0;
}
Read More +
解題區►解題區 - UVa

UVa 1364 - Knights of the Round Table

Problem

圓桌武士要圍一桌，由於騎士很多，他們彼此憎恨的關係也越來越複雜，梅林被聘請來計劃會議的圓桌位置，騎士們的座位必須符合下列條件，否則將會無法開會。

  • 彼此憎恨的騎士不可相鄰
  • 圓桌要恰好奇數個人，否則無法進行投票

由於是圓桌，每個騎士都恰好有兩個鄰居，梅林只想知道誰絕對沒有辦法參與圓桌，求出絕對無法參與圓桌會議的騎士個數，並不用最大化圓桌的最大人數。

Sample Input

1
2
3
4
5
6
7
5 5
1 4
1 5
2 5
3 4
4 5
0 0

Sample Output

1
2

Solution

首先，一個簡單的特性，二分圖如果存在環，則保證沒有奇環，因為從 X 集合出去到 Y 集合，再回到 X 集合，保證環的路徑一定經過偶數條邊。同時，存在奇環的圖，一定不是二分圖。

二分圖不存在奇環，存在奇環的圖一定不是二分圖

藉由這個道理，這題還需要點特性，如果這張圖存在奇環，對於一個 BCC (雙向連通元件)，則滿足所有點都可以在一個奇環上。有可能一個點同時在奇環或者是偶環。

這個證明也很簡單，BCC 在元件中，定義拿走任一條邊 e(u, v)，u 和 v 之間仍然存在一條路徑。那麼可以知道對於一個奇環上的點 x 和 y，以及奇環外一點 u，若 e(x, u) 存在，則 e(u, y) 也存在，則會產生兩個環，其中一個環一定是奇數。擴散下去，所有在 BCC 元件的點，都會在一個奇環上。

BCC 存在奇環，每一個點都至少在一個奇環上

很久沒寫 BCC，一直以來寫 cut point (關節點) 和 cut edge (bridge) 的機會比較高，都忘了 BCC 的寫法。一張圖，拆成 BCC 時，每一個節點可能存在數個 BCC 元件中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
// BCC
#include <stdio.h> 
#include <string.h>
#include <vector> 
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 1024;
class BCC {
public:
	vector<int> g[MAXN], bcc[MAXN];
	stack< pair<int, int> > stk;
	int n;
	int vfind[MAXN], findIdx;
	int visited[MAXN];
	int bcc_tmp[MAXN], bccCnt, cutPt[MAXN];
	int dfs(int u, int p) {
		visited[u] = 1;
		vfind[u] = ++findIdx;
		
		int mn = vfind[u], branch = 0, t;
		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i];
			if (!visited[v]) {
				stk.push(make_pair(u, v));
				t = dfs(v, u);
				mn = min(mn, t), branch++;
				if (t >= vfind[u]) {
					pair<int, int> e;
					bcc[++bccCnt].clear();
					do {
						e = stk.top(), stk.pop();
						if (bcc_tmp[e.first] != bccCnt)
							bcc[bccCnt].push_back(e.first), bcc_tmp[e.first] = bccCnt;
						if (bcc_tmp[e.second] != bccCnt)
							bcc[bccCnt].push_back(e.second), bcc_tmp[e.second] = bccCnt;
					} while (e != make_pair(u, v));
					cutPt[u] = 1;
				}
			} else if (vfind[v] < vfind[u] && v != p) {
				stk.push(make_pair(u, v));
				mn = min(mn, vfind[v]);
			}
		}
		if (p < 0 && branch == 1)	cutPt[u] = 0;
		return mn;
	}
	void findBCC() {
		while (!stk.empty())	stk.pop();
        memset(visited, 0, sizeof(visited));
        memset(bcc_tmp, 0, sizeof(bcc_tmp));
        bccCnt = 0;
        for (int i = 0; i < n; i++) {
			if (!visited[i]) {
				findIdx = 0;
				dfs(i, -1);
			}
		}
	}
	void addEdge(int x, int y) {
		g[x].push_back(y), g[y].push_back(x);
	}
	void init(int n) {
		this->n = n;
		for (int i = 0; i < n; i++)
			g[i].clear();
	}
} g;
int A[MAXN][MAXN];
int belong[MAXN], color[MAXN];
int isBipartite(int u) {
	for (int i = 0; i < g.g[u].size(); i++) {
		int v = g.g[u][i];
		if (belong[u] != belong[v])	
			continue;
		if (color[v] == color[u])
			return false;
		if (!color[v]) {
			color[v] = 3 - color[u];
			if (!isBipartite(v))
				return false;
		}
	}
	return true;
}
int main() {
	int n, m, x, y;
	while (scanf("%d %d", &n, &m) == 2 && n) {
		memset(A, 0, sizeof(A));
		for (int i = 0; i < m; i++) {
			scanf("%d %d", &x, &y), x--, y--;
			A[x][y] = A[y][x] = 1;
		}
		
		g.init(n);
		for (int i = 0; i < n; i++) {
			for (int j = i+1; j < n; j++) {
				if (!A[i][j]) {
					g.addEdge(i, j);
//					printf("%d %d --\n", i, j);
				}
			}
		}
		
		g.findBCC();
		
		memset(belong, 0, sizeof(belong));
		int onOddCycle[MAXN] = {};
		for (int i = 1; i <= g.bccCnt; i++) {
			for (int j = 0; j < g.bcc[i].size(); j++) {
				belong[g.bcc[i][j]] = i, color[g.bcc[i][j]] = 0;
//				printf("%d ", g.bcc[i][j]);
			}
//			puts("");
			memset(color, 0, sizeof(color));
			color[g.bcc[i][0]] = 1;
			if (!isBipartite(g.bcc[i][0])) { // 
				for (int j = 0; j < g.bcc[i].size(); j++)
					onOddCycle[g.bcc[i][j]] = 1;
			}
		}
		
		int ret = n;
		for (int i = 0; i < n; i++)
			ret -= onOddCycle[i];
		printf("%d\n", ret);
	}
	return 0;
}
/*
7 9
1 2
2 3
3 1
1 4
4 5
5 1
1 6
6 7
7 1
4 5
1 2
2 3
3 4
4 1
2 4
4 4
1 2
2 3
3 1
1 4
5 5
1 4
1 5
2 5
3 4
4 5
12 3
8 7
2 3
4 2
7 12
4 7
5 6
1 7
2 1
1 3
2 7
5 1
6 3
6 7
3 7
3 4
4 1
0 0
*/
Read More +
手札日記

停滯的日子

反正也沒什麼人關注，這篇就跟著之前內容隨興寫寫。

說一聲，最近沒有更新 BLOG，其解題代碼都直接送至 GitHub Repo UVa 中，同時要墮落於學校課程，寫 Big Data 作業折騰很久，隨後要開始進行 Game Maker 軟體使用，之後又要看學校課程的論文，交心得了事，最近的行程是這樣安排。

首先，這學期仍然沒有去實習，因為修了四天的課，「 明明是個大四？ 」，的確修了四天的系上選修，但是選課不盡人意，最後一學期初選果斷一門課也沒有，以前都是只中體育跟通識，系上選修課還真是難搶，結果就上了不怎麼喜歡的選修課。不過也就這樣吧，反正大學也失敗。

剛開學的日子，寫了點題目，玩了下 python，沒有到可以 UVa 解題的程度，一行程式果然不適合我，第一次實戰拿來玩 Big Data 的預處理資料分析，事實上用 Java 就能辦到。

隨著大家關心我研究所的事，當然心中充滿了掙扎，不是我願意不找教授，我有資格找教授嗎？這大學能讓我畢業嗎？很多人會覺得莫名奇妙，明明上了還不行動。讓我死在這裡吧。

Read More +