| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:为什么会错呢?搞不懂,哪位大侠帮着看看!谢谢!In Reply To:为什么会错呢?搞不懂,哪位大侠帮着看看!谢谢! Posted by:lyf_2009 at 2011-06-16 18:56:59 #include <vector>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
const int M = 4010;
bool vis[M];
int idx;
int Stop;
int n;
vector<int> table[M], marriage[2010];
bool isInStack[M];
int low[M];
int dfn[M];
int stack[M];
#define min(a, b) ((a)<(b)?(a):(b))
void tarjan(int u)
{
if (vis[u])
return;
vis[u] = true;
stack[Stop++] = u;
isInStack[u] = true;
low[u] = dfn[u] = idx++;
int i, v;
int size = table[u].size();
for (i = 0; i < size; i++)
{
v = table[u][i];
if (!vis[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (isInStack[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
vector<int> son, girl;
int person;
do
{
person = stack[--Stop];
isInStack[person] = false;
if (person <= n)
son.push_back(person);
else
girl.push_back(person);
}while (u != person);
int i, j, k;
for (i = 0; i < son.size(); i++)
{
k = son[i];
for (j = 0 ; j < girl.size(); j++)
{
marriage[k].push_back(girl[j]);
}
}
}
}
void initialize()
{
idx = 0;
Stop = 0;
memset(vis, 0, sizeof(vis));
memset(isInStack, 0, sizeof(isInStack));
}
int main()
{
int i, j, girl, num;
scanf("%d", &n);
initialize();
for (i = 1; i <= n; i++)
{
scanf("%d", &num);
for (j = 0; j < num; j++)
{
scanf("%d", &girl);
table[i].push_back(girl+n);
}
}
for (i = 1; i <= n; i++)
{
scanf("%d", &girl);
table[girl + n].push_back(i);
}
for (i = 1; i <= 2*n; i++)
tarjan(i);
for (i = 1; i <= n; i++)
{
sort(marriage[i].begin(), marriage[i].end());
int size = marriage[i].size();
printf("%d", size);
for (j = 0; j < size; j++)
printf(" %d", marriage[i][j]-n);
printf("\n");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator