POJ(2942)(Knights|POJ(2942)(Knights of the Round Table )
【POJ(2942)(Knights|POJ(2942)(Knights of the Round Table )】链接：https://vjudge.net/problem/POJ-2942
思路：本来算是一个多个算法的综合模板题，但是我不熟悉就拿来熟悉模板了，大概就是先用tarjan求出双连通分量，然后利用二分图对每个分量染色，并将能成功染色（必定为奇圈）的顶点标记，最后没标记的点就不能参加会议
代码：
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1001;
vector G[1001],bcc[1001];
int odd[1001],color[1001];
int dfn[1001];
int low[1001];
int iscut[1001];
int bccno[1001];
int ntime;
int n,m,bcc_cnt;
struct edge{
int u,v;
edge(){}
edge(int uu,int vv):u(uu),v(vv){}
};
deque edges;
//tarjan模板
void tarjan(int u,int f){
int i,j,k;
int child = 0;
//low在这里代表非父边所能连到的最早的结点的时间（与求强连通分量时候的low数组意思不一样，一定注意！），dfn表示该结点的开始搜索时间，初始时间dfn等于low
low[u] = dfn[u] = ++ntime;
for(i=0;
i 推荐阅读
- 模板 poj2947 Widget Factory 高斯消元
- POJ 1027 The Same Game 模拟题
- POJ 2728 Desert King(最优比率生成树)
- 图论|POJ1364 King 差分约束
- POJ 1364 King 差分约束系统
- poj2728|poj2728 Desert King
- SPOJ DISUBSTR - Distinct Substrings or SUBST1 - New Distinct Substrings 【不同子串数目】
- POJ|POJ2728 Desert King
- OJ|POJ 2686 Traveling by Stagecoach (状态压缩DP)
- poj|poj 8469 特殊密码锁