link :http://acm.timus.ru/problem.aspx?space=1&num=1106
describe : Yes n(n<=100) personal , Everyone has one or more friends ( Friendship is mutual ). Divide them into two groups , Make each group have friends in another group .

Ideas : The main idea is to find a subgraph so that it is a bipartite graph . Direct use dfs dyeing . It's not actually a bipartite graph , Because each subset of this problem can be connected by edges , As long as the conditions given by the title are met . It's a little simpler than bipartite graphs .

//g++ 4.7.2

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int M = 100 + 10;
int color[M], vis[M]; //color[i] Represents a node i The color of the ,1 According to black ,2 white
vector<int> G[M];
void dfs(int u)
{
vis[u] = 1;
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
if (!vis[v])
{
color[v] = 3 - color[u];
dfs(v);
}
}
}
int main()
{
int n, t;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
while (scanf("%d", &t) && t)
{
G[i].push_back(t);
}
memset(vis, 0, sizeof(vis));
memset(color, 0, sizeof(color));
for (int i = 1; i <= n; ++i)
if (!vis[i])
{
color[i]=1; // The starting point of each new connected component should be set to 1
dfs(i);
}
int sum = 0;
for (int i = 1; i <= n; ++i)
if (color[i] == 1)
++sum;
printf("%d\n", sum);
for (int i = 1; i <= n; ++i)
if (color[i] == 1)
printf("%d ", i);
return 0;
}

There's another way that's more or less , Look like dfs The actual is not , This problem only needs to dye the adjacent points of each node , You don't need recursion .

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int M = 100 + 10;
int color[M], vis[M];
vector<int> G[M];
void coloring(int u)
{
vis[u] = 1;
color[u] = 1;
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
if (!vis[v])
color[v] = 3 - color[u];
vis[v] = 1;
}
}
int main()
{
int n, t;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
while (scanf("%d", &t) && t)
{
G[i].push_back(t);
}
memset(vis, 0, sizeof(vis));
memset(color, 0, sizeof(color));
for (int i = 1; i <= n; ++i)
if (!vis[i])
coloring(i);
int sum = 0;
for (int i = 1; i <= n; ++i)
if (color[i] == 1)
++sum;
printf("%d\n", sum);
for (int i = 1; i <= n; ++i)
if (color[i] == 1)
printf("%d ", i);
return 0;
}

ural 1106. Two Teams More articles on bipartite graph coloring

  1. URAL 1106 Two Teams Bipartite graph

    S - Two Teams Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u Submi ...

  2. ural 1106 Two Teams

    http://acm.timus.ru/problem.aspx?space=1&num=1106 #include <cstdio> #include <cstring&g ...

  3. URAL 1106 Two Teams (DFS)

    The question There are in the group N personal , Everyone has one or more friends in the group . Divide the group into two teams , Any member of each team has at least one friend in the other team . Ideas At the beginning, I felt that it was the same as what I did a few days ago 2-sat( Any two members of each team must ...

  4. NOIP2008 Double stack sorting [ Dichotomous coloring | Stack |DP]

    Title Description Tom Recently, I am studying an interesting sorting problem . As shown in the figure , adopt 2 Stack S1 and S2,Tom Hope to use the following 4 Operations to sort the input sequence in ascending order . operation a If the input sequence is not empty , Push the first element onto the stack S1 operation b If the stack S1 ...

  5. Luogu P1330 Blockade sunshine University [ Dichotomous coloring ]

    Title Description Cao is an old Cao who loves to brush the streets , During the summer vacation , Every day he happily brushes the street on the campus of sunshine University . River crab sees happy Cao , Feel uncomfortable . River crab decided to block sunshine University , Don't let Cao brush the streets . The campus of sunshine university is a picture by N An undirected graph composed of two points ,N Between the two points by M ...

  6. POJ2942 Knights of the Round Table[ Point biconnected component | Dichotomous coloring | Make up a picture ]

    Knights of the Round Table Time Limit: 7000MS   Memory Limit: 65536K Total Submissions: 12439   Acce ...

  7. 【POJ 2942】Knights of the Round Table( Point biconnected component , Dichotomous coloring )

    The round table must satisfy : An odd number of people participate in , The neighbor can't be the enemy ( The enemy relationship is boundless ). Ask for the number of knights who can't attend the meeting in any case . Just need to know which knights are allowed to join . Let's find the complement of the original graph : As long as two people who are not the enemy are connected . In an odd part of the complement graph ...

  8. Codeforces Round #311 (Div. 2) D - Vitaly and Cycle( Application of bipartite graph coloring )

    http://www.cnblogs.com/wenruo/p/4959509.html Give a picture ( Not necessarily connected graphs , There are no double edges and self rings ), How many edges do you need to add to make a ring of odd length , And the number of schemes with the least edges . It's very tolerant ...

  9. SGU 172.eXam( Dichotomous coloring )

    The time limit :0.25s Space restriction :4M The question : take n(n<200) The points are divided into two sets , give m(m<=30000) Yes, not at the point of a set , Judge whether it can be divided into sets that meet the requirements , Output one of the sets and the total number of sets ...

Random recommendation

  1. Eclipse On GIT plug-in unit EGIT User manual

    http://blog.csdn.net/luckarecs/article/details/7427605 Eclipse On GIT plug-in unit EGIT User manual   One _ install EGIT plug-in unit http://dow ...

  2. iOS Not ARC Basic memory management series 1- Reference counter

    1. What is memory management Mobile devices have extremely limited memory , Every app There is a limit to the amount of memory that can be used When app When more memory is used , The system issues a memory warning , At this time, we have to reclaim some memory space that we no longer need to use . For example, recycling objects that don't need to be used . Variable ...

  3. WebBrowser Control to access page content across domains

    The source of the original text is  :http://blog.csdn.net/nocky/article/details/6056802 Source code :http://www.codecentrix.com/blog/wnd2do ...

  4. Webapi call

    C# webapi Route name cannot follow area The same name , Otherwise appear 404 action Problems that can't be found ???

  5. [ turn ] frequently-used CSS Naming rules

    ( One ) frequently-used CSS Naming rules    head :header   Content :content/container   tail :footer   Navigation :nav   Sidebar :sidebar   The column :column   The page periphery controls the overall layout width ...

  6. C Language Check : File operations

    File operation topic C The concept of language file reading and writing Document classification According to the logical structure of the file : Log files : It consists of records with a certain structure ( Fixed length and indefinite length ) Streaming files : By characters ( byte ) The data sequence consists of Press storage media : Ordinary documents : Storage media files ( magnetism ...

  7. Scala Use implicit conversion for comparison

    Boy.scala class Boy(val name: String, val faceValue: Int) extends Comparable[Boy]{ override def comp ...

  8. bzoj The thousand questions project 258:bzoj3123: [Sdoi2013] The forest

    http://www.lydsy.com/JudgeOnline/problem.php?id=3123 Heuristic merging chairman tree #include<cmath> #include<cstd ...

  9. angular Learning notes ( thirty )- Instructions (5)-link

    This article mainly introduces angular Directive link attribute : link:function(scope,iEle,iAttrs,ctrl,linker){ .... } link Property value is a function , This function has five parameters ...

  10. bzoj 3997 Dilworth Theorem

    I feel like network flow when I see this question , If there are no weights , It can be used DAG Minimum path coverage , There are weights , We can find an upper and lower bound minimum feasible flow , But the memory card is broken .... Time estimates are also up in the air . A positive solution requires some mathematical knowledge , Let's sort it out here : Definition : Partial order relation : ...