題意

小組里有N個(gè)人，每個(gè)人都有一個(gè)或多個(gè)朋友在小組里。將小組分成兩個(gè)隊(duì)伍，每個(gè)隊(duì)伍的任意一個(gè)成員都有至少一個(gè)朋友在另一個(gè)隊(duì)伍。

思路

一開始覺得和前幾天做過的一道2-sat（每個(gè)隊(duì)伍任意兩個(gè)成員都必須互相認(rèn)識(shí)）相似然后就往那邊想了……看了題解才發(fā)現(xiàn)這題很簡(jiǎn)單…… 我們注意到同組里的人是互不影響的，所以一個(gè)人如果已經(jīng)確定在哪組的話是不會(huì)對(duì)后面進(jìn)入這個(gè)組的人產(chǎn)生影響的。 所以我們按順序直接搜就可以了，每個(gè)人在他朋友里面找一個(gè)已經(jīng)確定組的，然后放到對(duì)面組。如果他的所有朋友都沒確定，把他隨便放一個(gè)組就行了。

代碼

? [java] import java.util.*; import java.util.Map.Entry; import java.math.*; public class Main{ static int group[] = new int [205]; static Vector <Vector> adj = new Vector <Vector> (); public static int divide(int p){ group[p+1] = -2; for (int j = 0; j < adj.get(p).size(); j ++){ int v = (int) adj.get(p).get(j); if (group[v] == -1){ return (group[p+1] = 1 - divide(v-1)); } if (group[v] > -1){ return (group[p+1] = 1 - group[v]); } } if (group[p+1] == -2) return (group[p+1] = 0); return 0; } public static void main(String args[]){ Scanner cin = new Scanner(System.in); int n = cin.nextInt(); for (int i = 1; i <= n; i ++){ int tmp = 0; Vector <Integer> tmpv = new Vector <Integer> (); while((tmp = cin.nextInt()) != 0){ tmpv.addElement(tmp); } adj.addElement(tmpv); } boolean ok = true; for (int i = 0; i < adj.size(); i ++){ group[i+1] = -1; if (adj.get(i).size() == 0){ ok = false; break; } } for (int i = 0; i < adj.size(); i ++){ group[i+1] = divide(i); } if (ok == false){ System.out.println("0"); } else{ Vector <Integer> ans = new Vector <Integer> (); for (int i = 1; i <= n; i ++){ if (group[i] == 0){ ans.addElement(i); } } System.out.println(ans.size()); for (int i = 0; i < ans.size(); i ++){ if (i > 0) System.out.print(" "); System.out.print(ans.get(i)); } System.out.println(""); } cin.close(); } } [/java]

轉(zhuǎn)載于:https://www.cnblogs.com/AbandonZHANG/p/4114349.html

總結(jié)

以上是生活随笔為你收集整理的URAL 1106 Two Teams (DFS)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。