题解：Kattis - Weak Vertices

Weak Vertices (weakvertices)

题目大意

给定一张无向图 $G$，找出所有不属于任何一个三元环的顶点。

解题思路

使用邻接矩阵记录图中所有的边，使用邻接表记录每个顶点的“邻居”顶点

某顶点 $V$ 在一个三元环上，当且仅当：

• $\deg(V) \ge 2$ （但这一点不用显式判断）
• $\exists (V, V_1), (V, V_2) \in G \Rightarrow (V_1, V_2) \in G$

即对顶点 $V$ 的所有邻居，判断它们之间是否有边相连。

参考代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<queue>
#include<algorithm>
#include<cmath>
#include<vector>
//#include<unordered_map>
//#define map unordered_map
#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#endif
using namespace std;
/*================*/

inline int read() {
	char c=getchar();int x=0,f=1;
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10+c-48;
	return x*f;
}

#define r(a) (a)=read()

int n;
vector<int> g[21];
int x;
bool mat[21][21];
bool ans[21];

signed main() {
	while (1) {
		r(n);
		if (n < 0)
			break;
		for (int i = 0; i < n; i++) {
			g[i].clear();
			ans[i] = 0;
		}
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (mat[i][j] = read()) {
					g[i].push_back(j);
				}
		for (int i = 0; i < n; i++) {
			for (int u = 0; u < g[i].size(); u++)
				for (int v = u + 1; v < g[i].size(); v++)
					if (mat[g[i][u]][g[i][v]]) {
						ans[i] = 1;
						goto nxt;
					}
			nxt:
		}
		for (int i = 0; i < n; i++)
			if (!ans[i])
				printf("%d ", i);
		printf("\n");
	}
	return 0;
}