运城网站建设,怎么做网站首页弹幕,网站编程设计如何写备注,同时做网站建设和代账如果出现遍历图中的某个点都是在奇数时刻或者偶数时刻#xff0c;那么小偷的藏点就是根据时间判定在某些的奇数点和偶数点了。 如果图出现奇数的环#xff0c;即#xff1a;有一个环由奇数个点组成#xff0c;那么环中的某个点在奇数和偶数时刻都能到达(可以画图试试)。其实… 如果出现遍历图中的某个点都是在奇数时刻或者偶数时刻那么小偷的藏点就是根据时间判定在某些的奇数点和偶数点了。 如果图出现奇数的环即有一个环由奇数个点组成那么环中的某个点在奇数和偶数时刻都能到达(可以画图试试)。其实奇数环导致小偷藏点无规律的最大原因是 在遍历最后奇数环的两个(必定是两个)未遍历点的时候他们是同奇(偶)的然而还有一条边直接相连。导致在下一时刻那两个点又可以同时变成偶(奇)。如果在回溯遍历的话就会出现整张图在奇数时刻或者偶数时刻都能到达。 无向图G为二部图的充分必要条件是G至少有两个顶点且其所有回路的长度均为偶数。 如果我们把图中奇数时刻能够到达的点归到X集合偶数能到点归到Y集合那么如果图中出现相同集合的点有 边相连那么就不满足二分图的性质即可输出YES如果原图可二分图话答案就是NO了。 然后就是经典的二分图判定。 CODE #includeiostream#includecstdio#includealgorithm#includecstringusing namespace std;const int MAXN 100010;const int MAXM 500010;struct Edge{ int v, next;}edge[MAXM];int n, m, s;int cnt;int first[MAXN];bool color[MAXN], vis[MAXN];void init(){ cnt 0; memset(vis, 0, sizeof(vis)); memset(color, 0, sizeof(color)); memset(first, -1, sizeof(first));}void read_graph(int u, int v){ edge[cnt].v v; edge[cnt].next first[u], first[u] cnt;}int find(int u){ for(int e first[u]; e ! -1; e edge[e].next) { int v edge[e].v; if(!vis[v]) { vis[v] 1; color[v] !color[u]; find(v); } else if(color[u] color[v]) return false; } return true;}int main(){ int T, times 0; scanf(%d, T); while(T--) { init(); scanf(%d%d%d, n, m, s); while(m--) { int u, v; scanf(%d%d, u, v); read_graph(u, v); read_graph(v, u); } printf(Case %d: , times); color[s] 1; vis[s] 1; printf(find(s)?NO\n:YES\n); } return 0;} 转载于:https://www.cnblogs.com/g0feng/archive/2012/11/02/2751598.html
