Portal :Problem 1904

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

Reference material :

[1]:http://www.cnblogs.com/frog112111/p/3384261.html

[2]:https://blog.csdn.net/a709743744/article/details/52133778

[3]:http://www.cppblog.com/Uriel/articles/121169.html

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]; void addEdge(int u,int v)
{
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");
}
}

There's no input-output link

 #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]; void addEdge(int u,int v)
{
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

    A practical example of thread processing : @Service public class SynAsynThreadTestServiceImpl implements SynAsynThreadTestService ...

  9. NABCD frame ( Regular reminders of assignments and events ) And the eighth week learning progress bar

    NABCD frame ( Regular reminders of assignments and events ): N(need, demand ): What needs of users have your creativity solved ? Our creativity can urge our users to a certain extent ( Student ) Finish your recent task or homework as soon as possible . We think that if we add a fixed time ...

  10. babel-polyfill

    babel-polyfill Babel Only new is converted by default JavaScript syntax (syntax), Instead of converting new ones API, such as Iterator.Generator.Set.Maps.Proxy.Reflec ...