Portal :Problem 1904

https://www.cnblogs.com/violet-acmer/p/9739990.html

Reference material ：

The question ：

Yes n A prince , Every prince has k A favorite girl , Every prince can only marry his favorite sister , The minister gives a matching table , Every prince marries a sister , But the king was not satisfied , He asked the minister to give him another watch , How many girls can each Prince marry , Output the number of girls in ascending order , This watch should satisfy all princes that they will eventually have a sister to marry him .

analysis ：

Good graph thesis , Combining strong connected components with perfect matching .

2*N Vertex 2 Subgraph , And gave a perfect match (Perfect Matching) And other vertices that each vertex can connect to .

Is it possible to determine whether 2 After connecting two vertices to each other , other 2*(N - 1) Vertex 2 Whether a partition can form a perfect match .

Drawing ：

If the prince u I like my sister v, Then build an edge u Point to v(u,v), For the prime minister's initial perfect match , If the prince u With my sister v marry , Then build an edge v Point to u(v,u), Then we find the strongly connected component .

For every prince and sister , If they're all in the same strongly connected component , Then they can get married .

Why? ？ Because every prince can only marry his favorite sister , In the initial perfect match, there are two different sides between husband and wife that can reach each other , Then the number of princes and sisters in the same strongly connected component must be equal , If Prince x You can talk to another girl a marry , sister a My original Prince y I'm sure we'll find another girl b marry , Because if you can't find it , be x and a It must not be in the same strongly connected component .

So a prince can marry all his sisters who share the same strong connection with him , And that doesn't lead to other princes in the same strong connectivity component not getting married .

（ prove ： Why can't princes choose girls with different strong connectivity components ：

Reduction to absurdity ： If the strongly connected component 1 The prince in chose the strongly connected component 2 My sister in the movie , So it's bound to be strongly connected 2 One of the princes can't find a sister in his own strong connection component , Then he will go to other places to find his sister , It goes on and on , We know that in the end it must be through the strongly connected component 1,2,x1,x2,xn,……,1, Princes can find their own girls , So these strongly connected components 1,2,x1,x2,xn,……,1 It makes up a strongly connected component , It's not consistent with the problem of finding sister in different strong connected components ）

The difficulty of this problem ： Drawing

AC Code ：

There is a large amount of data on this question , Just input and output will consume a lot of time , You can use the I / O plug-in to speed up the read in and output .

Kosaraju Algorithm ：

``` #include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
#define mem(a,b) memset(a,b,sizeof a)
#define pb push_back
const int maxV=4e3+;
int scc[maxV];
bool vis[maxV];
vector<int >vs;
vector<int >edge[maxV],redge[maxV];
{
edge[u].pb(v);
redge[v].pb(u);
}
void Dfs(int u)
{
vis[u]=true;
for(int i=;i < edge[u].size();++i)
{
int to=edge[u][i];
if(!vis[to])
Dfs(to);
}
vs.pb(u);
}
void rDfs(int u,int sccId)
{
scc[u]=sccId;
vis[u]=true;
for(int i=;i < redge[u].size();++i)
{
int to=redge[u][i];
if(!vis[to])
rDfs(to,sccId);
}
}
void Scc(int maxV)
{
mem(vis,false);
vs.clear();
for(int i=;i <= maxV;++i)
if(!vis[i])
Dfs(i);
mem(vis,false);
int sccId=;
for(int i=vs.size()-;i >= ;--i)
{
int v=vs[i];
if(!vis[v])
{
sccId++;
rDfs(v,sccId);
}
}
}
int main()
{
int N;
scanf("%d",&N);
for(int i=;i <= N;++i)
{
int k,v;
scanf("%d",&k);
while(k--)
{
scanf("%d",&v);
addEdge(i,v+N);// prince i I like my sister v
}
}
for(int i=;i <= N;++i)
{
int v;
scanf("%d",&v);
addEdge(v+N,i);// prince i I can talk to my sister v marry
}
Scc(N);
for(int i=;i <= N;++i)
{
int res=;
int ans[maxV];
for(int j=;j < edge[i].size();++j)
{
int to=edge[i][j];
if(scc[i] == scc[to])// The same strongly connected component
ans[res++]=to;
}
sort(ans,ans+res);
printf("%d",res);
for(int j=;j < res;++j)
printf(" %d",ans[j]-N);
printf("\n");
}
}```

``` #include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
#define mem(a,b) memset(a,b,sizeof a)
#define pb push_back
const int maxV=4e3+;
int scc[maxV];
bool vis[maxV];
vector<int >vs;
vector<int >edge[maxV],redge[maxV];
{
edge[u].pb(v);
redge[v].pb(u);
}
void Dfs(int u)
{
vis[u]=true;
for(int i=;i < edge[u].size();++i)
{
int to=edge[u][i];
if(!vis[to])
Dfs(to);
}
vs.pb(u);
}
void rDfs(int u,int sccId)
{
scc[u]=sccId;
vis[u]=true;
for(int i=;i < redge[u].size();++i)
{
int to=redge[u][i];
if(!vis[to])
rDfs(to,sccId);
}
}
void Scc(int maxV)
{
mem(vis,false);
vs.clear();
for(int i=;i <= maxV;++i)
if(!vis[i])
Dfs(i);
mem(vis,false);
int sccId=;
for(int i=vs.size()-;i >= ;--i)
{
int v=vs[i];
if(!vis[v])
{
sccId++;
rDfs(v,sccId);
}
}
}
//=============== I / O hang ===============
int Scan() // Input plug-in
{
int res=,ch,flag=;
if((ch=getchar())=='-')
flag=;
else if(ch>=''&&ch<='')
res=ch-'';
while((ch=getchar())>=''&&ch<='')
res=res*+ch-'';
return flag?-res:res;
}
void Out(int a) // Output plug-in
{
if(a>)
Out(a/);
putchar(a%+'');
}
//========================================
int main()
{
int N;
scanf("%d",&N);
for(int i=;i <= N;++i)
{
int k,v;
//scanf("%d",&k);
k=Scan();
while(k--)
{
//scanf("%d",&v);
v=Scan();
addEdge(i,v+N);// prince i I like my sister v
}
}
for(int i=;i <= N;++i)
{
int v;
//scanf("%d",&v);
v=Scan();
addEdge(v+N,i);// prince i I can talk to my sister v marry
}
Scc(N);
for(int i=;i <= N;++i)
{
int res=;
int ans[maxV];
for(int j=;j < edge[i].size();++j)
{
int to=edge[i][j];
if(scc[i] == scc[to])// The same strongly connected component
ans[res++]=to;
}
sort(ans,ans+res);
//printf("%d",res);
Out(res);
for(int j=;j < res;++j)
{
printf(" ");
Out(ans[j]-N);
//printf(" %d",ans[j]-N);
}
printf("\n");
}
}```

Call I / O hook

It's too late , Exhaustion of body and mind , I'll make it up tomorrow Tarjan Algorithm ...............

## poj 1904( Strong connected components + Perfect match ) More articles about

1. POJ 1904 King&#39;s Quest ( Strong connected components + Perfect match )

< Topic link > The main idea of the topic : Yes n A prince , Every prince has k A favorite girl , Every prince can only marry his favorite sister , The minister gives a matching table , Every prince marries a sister , But the king was not satisfied , He asked the minister to give him another watch , Every king ...

2. poj 1904( Strong connected components + I / O plug in )

Topic link :http://poj.org/problem?id=1904 The question : Yes n A prince , Every prince has k A favorite girl , Every prince can only marry his favorite sister , The minister gives a matching table , Every prince marries a sister , But the country ...

3. poj 1904 Strong connected components

Ideas : First of all, every son builds a border with all the girls he likes , For the correct match given at the end , We built the side from the girl to the corresponding Prince . In the same strongly connected component as a prince , And the girls that the prince likes are all the girls that the prince can marry . The idea is similar to the Hungarian algorithm for matching , You can always find an extension ...

4. poj 2186 Strong connected components

poj 2186 Strong connected components Portal Popular Cows Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 33414 Acc ...

5. poj 2762( Strong connected components + A topological sort )

Topic link :http://poj.org/problem?id=2762 The question : Let's give a digraph , Judge any two vertices (u,v) Power on u arrive v, or v arrive u, Simply connected , Output Yes or No. analysis : For the same strong link ...

6. poj 1236( Strong connected component decomposition template problem )

Portal The question : N(2<N<100) There is a one-way network between the two schools , After each school gets a set of software , It can be transmitted to the surrounding schools through one-way network . problem 1: At least how many schools need to be distributed the software initially , So that all the schools in the network will eventually ...

7. POJ(2186) Strongly connected component decomposition

#include<cstdio> #include<vector> #include<cstring> using namespace std; ; vector& ...

8. Popular Cows POJ - 2186( Strong connected components )

Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10, ...

9. POJ 1904 King's Quest *( Strong connected components ： It's possible to match edges perfectly )

The question Yes n Two girls and n A boy , Given some relationships, boys like girls ( That is, two people can get married ), And given an initial match , Which girl does this boy marry , The initial match must be legal . Ask each boy and which girls can marry and can not have sex with everyone ...

## Random recommendation

1. Unity3D The preform in (Prefab) How to create and use ！！！

First of all, I'd like to explain what kind of preform ? stay U3D Inside we call it Prefab: We can think of it this way : When the game components are made ( Any one of the scenes gameobject), We want to make it a component template , For batch application work , For example, say field ...

2. android Road of development 03

One .Activity1. How to define multiple Activity:① Define a class , Inherit Activity:② In this category , make carbon copies Activity In the middle of onCreate Method :③ stay AndroidManifes ...

3. Android performance optimization --- Layout optimization

We are engaged in Android When developing and writing layouts, most of them use XML Layout , This brings us convenience , This operation can lay out the code and logic control of the interface Java Code separation , Make the structure of the program clearer . clear . A particularly complex layout , But this ...

4. Shopping mall project arrangement （ Four ）JDBC+ Rich text editor to increase goods , The style is set , And modify

UEditor Rich text editor :http://ueditor.baidu.com/website/ The corresponding page shows : Add : Commodity modification : Front desk display : Commodity TABLE CREATE TABLE statement : create table TE ...

5. python_19_ exception handling

What is exception handling ? -- For user input , Don't want users to see error messages , Handle exceptions What is the framework for exception handling ? try: Programs that can go wrong 1 Programs that can go wrong 2        # Program 1 Something went wrong , Not executing the program 2 exc ...

6. linux Of cron

linux System consists of cron(crond) This system service controls ,linux There used to be a lot of planned work on the system , therefore , This system service is started by default .cron The process periodically checks every minute for any tasks to be performed , If there is, it will be executed automatically ...

7. BrupSuite Penetration test notes （ Ten ）

One .Brup Repeater Usually combined with Proxy( Historical record ),Scanner( Scanning records ).Target( Site map ) etc. , Right click on other tools to execute [Send to Repeater], Then jump to Repea ...

8. springboot Project threads use 2