记录信息
评测状态    Accepted
题目  P1022 Victoria的舞会2
递交时间    2016-08-09 15:48:04
代码语言    C++
评测机 ShadowShore
消耗时间    0 ms
消耗内存    552 KiB
评测时间    2016-08-09 15:48:06
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 544 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 548 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 544 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 548 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 548 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 548 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 544 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 548 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 552 KiB, score = 10
Accepted, time = 0 ms, mem = 552 KiB, score = 100
代码
#include <algorithm>
#include <cstdio>
#include <cstring>
using std :: min;
int n,m;
bool s[201][201],v[201];
void floyd() {
  for (int k = 1;k <= n;k++)
    for (int i = 1;i <= n;i++)
      for (int j = 1;j <= n;j++)
        if (s[i][k] && s[k][j]) s[i][j] = true;
}
int main() {
  memset(s,false,sizeof(s));
  scanf("%d",&n);
  int x;
  for (int i = 1;i <= n;i++)
    while (scanf("%d",&x),x != 0)
      s[i][x] = true;
  floyd();
  int ans = 0;
  memset(v,true,sizeof(v));
  for (int i = 1;i <= n;i++)
    if (v[i]) {
      for (int j = 1;j <= n;j++)
        if (j != i && s[i][j] && s[j][i])
          v[j] = false;
      ans++;
      v[i] = false;
    } 
  printf("%d",ans);
  return 0;
}

#include <algorithm>
#include <cstdio>
#include <cstring>
using std :: min;
int n,m;
bool s[201][201],v[201];
void floyd() {
for (int k = 1;k <= n;k++)
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
if (s[i][k] && s[k][j]) s[i][j] = true;
}
int main() {
memset(s,false,sizeof(s));
scanf("%d",&n);
int x;
for (int i = 1;i <= n;i++)
while (scanf("%d",&x),x != 0)
s[i][x] = true;
floyd();
int ans = 0;
memset(v,true,sizeof(v));
for (int i = 1;i <= n;i++)
if (v[i]) {
for (int j = 1;j <= n;j++)
if (j != i && s[i][j] && s[j][i])
v[j] = false;
ans++;
v[i] = false;
}
printf('%d',ans);
return 0;
}

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;

int main(){
int n;
bool check[201][201];
memset(check, false, sizeof(check));

cin>>n;
for(int i=0; i<n; i++){
int tmp;
while(cin>>tmp && tmp)
check[i][tmp-1] = true;
}

//shortest path
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
for(int k=0; k<n; k++)
check[j][k] = check[j][k] || (check[j][i] && check[i][k]);

bool flag[205];
int res = 0;
int counter = n;
memset(flag, true, sizeof(flag));
while(counter > 0){
queue<int> q;
for(int i=0; i<n; i++){
if(flag[i] == true){
q.push(i);
counter--;
flag[i] = false;
break;
}
}//end for loop
while(q.empty() == false){
int tmp = q.front();
q.pop();
for(int i=0; i<n; i++){
if(flag[i]==true
&& check[i][tmp]==true
&& check[tmp][i]==true){
flag[i] = false;
counter--;
q.push(i);

}
}
}//end while loop

res++;
}
cout<<res<<endl;
return 0;
}

//c++语言写的

我用的是tarjan算法。。。求强联通分量的数目，一开始也想到并查集了，但不想写。
测试数据 #0: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 856 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 856 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 852 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 852 KiB, score = 10
Accepted, time = 0 ms, mem = 856 KiB, score = 100
代码：
var
side:array[0..200,0..200] of boolean;
stack,dfn,low:array[0..200] of longint;
v:array[0..200] of boolean;
deep,top,n,i,m,x,y,ans:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure tarjan(x:longint);
var
i:longint;
begin
inc(deep);
dfn[x]:=deep;low[x]:=deep;
inc(top);
stack[top]:=x;
v[x]:=true;
for i:=1 to n do
if side[x,i] then begin
if dfn[i]=0 then begin
tarjan(i);
low[x]:=min(low[x],low[i]);
end
else
if v[i] then low[x]:=min(low[x],dfn[i]);
end;
if dfn[x]=low[x] then begin inc(ans);
repeat
v[stack[top]]:=false;
dec(top);
until stack[top+1]=x;
end;
end;

begin
fillchar(side,sizeof(side),false);
readln(n);
for i:=1 to n do
begin
read(x);
while x<>0 do
begin
side[i,x]:=true;
read(x);
end;
end;
ans:=0;
top:=0;
deep:=0;
for i:=1 to n do
if dfn[i]=0 then tarjan(i);
writeln(ans);
end.

GY解题报告
//思路：裸的强连通分量
//代码：Kosaraju
using namespace std;
#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
#define maxn 200+10
#define maxm 200*200+100

int n,m,first[5][maxn],next[5][maxm],u[5][maxm],v[5][maxm],vis[maxn],ans;
stack<int>s;
struct f
{ int rank,father; }f[maxn];
void merge(int u,int v);

void dfs(int t,int flag)
{
int k=first[flag][t];
while(k!=-1)
{
if(vis[v[flag][k]]==0)
{
if(flag==2)
merge(u[flag][k],v[flag][k]);
vis[v[flag][k]]=1;
dfs(v[flag][k],flag);
}
k=next[flag][k];
}
if(flag==1)
s.push(t);
return;
}

int main()
{
freopen("P1022.in","r",stdin);

cin>>n;
memset(first[1],-1,sizeof(first[1]));m=0;
for(int i=1;i<=n;i++)
{
int t;cin>>t;
while(t!=0)
{
m++;
u[1][m]=i,v[1][m]=t;
next[1][m]=first[1][u[1][m]];first[1][u[1][m]]=m;
cin>>t;
}
}

memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
{
f[i].rank=1,f[i].father=i;
if(vis[i]==0)
{
vis[i]=1;
dfs(i,1);
}
}

memset(first[2],-1,sizeof(first[2]));
for(int i=1;i<=m;i++)
{
u[2][i]=v[1][i],v[2][i]=u[1][i];
next[2][i]=first[2][u[2][i]];first[2][u[2][i]]=i;
}

memset(vis,0,sizeof(vis));
while(!s.empty())
{
int t=s.top();
if(vis[t]==0)
{
vis[t]=1;
dfs(t,2);
}
s.pop();
}

ans=0;
for(int i=1;i<=n;i++)
if(f[i].father==i)
ans++;
cout<<ans<<endl;

return 0;
}

int getf(int v)
{
if(f[v].father==v)
return v;
else
{
f[v].father=getf(f[v].father);
return f[v].father;
}
}

void merge(int u,int v)
{
int t1=getf(u);int t2=getf(v);
if(t1!=t2)
{
if(f[t1].rank=f[t2].rank)
{
f[t2].father=t1;f[t1].rank+=f[t2].rank;
}
else
{
f[t1].father=t2;f[t2].rank+=f[t1].rank;
}
}
}

非常简洁的代码

#include <algorithm>
#include <cstdio>
#include <cstring>
using std :: min;
int n,m;
bool s[201][201],v[201];
void floyd() {
  for (int k = 1;k <= n;k++)
    for (int i = 1;i <= n;i++)
      for (int j = 1;j <= n;j++)
        if (s[i][k] && s[k][j]) s[i][j] = true;
}
int main() {
  memset(s,false,sizeof(s));
  scanf("%d",&n);
  int x;
  for (int i = 1;i <= n;i++)
    while (scanf("%d",&x),x != 0)
      s[i][x] = true;
  floyd();
  int ans = 0;
  memset(v,true,sizeof(v));
  for (int i = 1;i <= n;i++)
    if (v[i]) {
      for (int j = 1;j <= n;j++)
        if (j != i && s[i][j] && s[j][i])
          v[j] = false;
      ans++;
      v[i] = false;
    } 
  printf("%d",ans);
  return 0;
}

#include <algorithm>
#include <cstdio>
#include <cstring>
using std :: min;
int n,m;
bool s[201][201],v[201];
void floyd() {
for (int k = 1;k <= n;k++)
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
if (s[i][k] && s[k][j]) s[i][j] = true;
}
int main() {
memset(s,false,sizeof(s));
scanf("%d",&n);
int x;
for (int i = 1;i <= n;i++)
while (scanf("%d",&x),x != 0)
s[i][x] = true;
floyd();
int ans = 0;
memset(v,true,sizeof(v));
for (int i = 1;i <= n;i++)
if (v[i]) {
for (int j = 1;j <= n;j++)
if (j != i && s[i][j] && s[j][i])
v[j] = false;
ans++;
v[i] = false;
}
printf("%d",ans);
return 0;
}

自学python的第一天...写了好久
```python 3
global Darr;
n=input();
n=int(n);
Father=[(i+1) for i in range(n)];
Darr=[[0 for i in range(n)] for j in range(n)]
Friends=[[False for i in range(n)] for j in range(n)];
for i in range(n):
num=input().split(' ');
Darr[i]=list(map(int,num));

global ArrStack,TopStack,ArrExistStack;
global TimeCnt;
global Ans;
global vis;
global Dfn,Low;
TimeCnt=0;
vis=[False for i in range(n)];
Low=[0 for i in range(n)];
Dfn=[0 for i in range(n)];
ArrStack=[0 for i in range(n)];
ArrExistStack=[0 for i in range(n)];
Ans=0;
TopStack=-1;
def Tarjan(u):
global Darr;
global TimeCnt;
global Ans;
global vis;
global Dfn,Low;
global ArrStack, TopStack, ArrExistStack;
vis[u-1]=True;
TimeCnt+=1;
Dfn[u-1]=Low[u-1]=TimeCnt;
TopStack+=1;
ArrStack[TopStack]=u;
ArrExistStack[u-1]=2;
for j in range(len(Darr[u-1])):
v=Darr[u-1][j];
if v==0:
break;
if not vis[v-1]:
Tarjan(v);
Low[u - 1] = min(Low[u - 1], Low[v - 1]);
elif ArrExistStack[v-1]==2:
Low[u-1]=min(Low[u-1],Low[v-1]);
if Dfn[u-1]==Low[u-1]:
Ans+=1;
while TopStack>=0:
ArrExistStack[ArrStack[TopStack]-1]=1;
TopStack-=1;
if ArrStack[TopStack+1]==u:
break;
for i in range(n):
if not vis[i]:
Tarjan(i+1);
print(Ans);
```

BFS
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 556 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 556 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 552 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 564 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 560 KiB, score = 10
Accepted, time = 0 ms, mem = 564 KiB, score = 100

代码
#include<cstdio>
#include<vector>
using namespace std;

template <typename T>
class arrayQueue {
public:
arrayQueue(int initialCapacity = 10) {
arrayLength = initialCapacity;
Queue = new T [arrayLength];
theFront = 0;
theBack = 0;
}
~arrayQueue() {
delete [] Queue;
}

T& front() {
return Queue[(theFront + 1) % arrayLength];
}
bool empty() {
return theFront == theBack;
}
void pop() {
theFront = (theFront + 1) % arrayLength;
Queue[theFront].~T();
}
void push(const T &element) {
theBack = (theBack + 1) % arrayLength;
Queue[theBack] = element;
}
private:
int theFront;
int theBack;
int arrayLength;
T *Queue;
};

const int MaxN = 200 + 10;

int N, M, K;
bool visit[MaxN];

vector <int> Graph[MaxN];
arrayQueue<int> Q(MaxN);

void BFS(const int &X) {
Q.push(X); visit[X] = 1;
while(!Q.empty()) {
int Now = Q.front(); Q.pop(); visit[Now] = 1;
for(vector<int>::iterator i = Graph[Now].begin(); i != Graph[Now].end(); ++i)
if(!visit[*i]) Q.push(*i);
}
}

int main() {
scanf("%d", &N);
for(int i = 1; i <= N; ++i)
while(scanf("%d", &K) == 1&& K)
Graph[i].push_back(K);
for(int i = 1; i <= N; ++i)
if(!visit[i]) {
++M; BFS(i);
}
printf("%d", M);
return 0;
}

Vijos数据这么水还能不能好好玩耍了。。。

并查集过的。。。打开标签一看是图结构顿时就醉了。。。。
上附代码

http://www.cnblogs.com/oierforever/p/4764704.html

P1022Victoria的舞会2
Accepted

记录信息

评测状态 Accepted
题目 P1022 Victoria的舞会2
递交时间 2015-07-07 22:52:22
代码语言 C++
评测机 VijosEx
消耗时间 30 ms
消耗内存 304 KiB
评测时间 2015-07-07 22:52:24

评测结果

编译成功

foo.cpp: In function 'void dfs(int)':
foo.cpp:34:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( i = 0 ; i < l[x].after.size() ; i++ )
^

测试数据 #0: Accepted, time = 0 ms, mem = 300 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 304 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 304 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 304 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 304 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 304 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 304 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 304 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 304 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 300 KiB, score = 10

Accepted, time = 30 ms, mem = 304 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <vector>
#include <stack>

using namespace std;

int m;
int n;
int dfn[1000 + 10];
int low[1000 + 10];
int visit[1000 + 2];
int cnt;
stack < int > st;
int i , j;

struct link
{
vector < int > after;
};

link l[1000 + 10];
bool instack[1000 + 10];
int a , b;
int ans;

void dfs( int x )
{
visit[x] = 1;
dfn[x] = low[x] = cnt++;
st.push( x );
instack[ x ] = 1;
int i;
for( i = 0 ; i < l[x].after.size() ; i++ )
{
if( !visit[ l[x].after[i] ] )
{
dfs( l[x].after[i] );
low[x] = min( low[x] , low[ l[x].after[i] ] );
}
else if( instack[ l[x].after[i] ] )
low[x] = min( low[x] , dfn[ l[x].after[i] ] );
}
int v;
if( low[x] == dfn[x] )
{
do
{
v = st.top();
instack[ v ] = 0;
st.pop();
}
while( v != x );
ans++;
}
}

int main()
{
cnt = 1;
scanf( "%d" , &n );
for( i = 1 ; i <= n ; i++ )
while( scanf( "%d" , &b ) != EOF )
{
if( !b )
break;
l[i].after.push_back( b );
}
for( i = 1 ; i <= n ; i++ )
if( !visit[i] )
dfs( i );
cout << ans << endl;
return 0;
}
就没有人用tarjan？

下一题和这一题一样
program p1022;
var a:array[1..200,1..200] of boolean;
b:array[1..200] of boolean;
n,i,j,k:integer;
c:boolean;
begin
readln(n);
fillchar(a,sizeof(a),false);
fillchar(b,sizeof(b),false);
for i:=1 to n do
begin
read(j);
while j<>0 do
begin
a[i,j]:=true;
read(j);
end;
readln;
end;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do a[i,j]:=a[i,j] or (a[i,k] and a[k,j]);
c:=false;
k:=0;
while not c do
begin
inc(k);
for i:=1 to n do
if not b[i] then break;
b[i]:=true;
for j:=1 to n do
if a[i,j] then b[j]:=true;
c:=true;
for i:=1 to n do
if not b[i] then
begin
c:=false;
break;
end;
end;
writeln(k);
end.

tarjan强连通 今天百度学了一下，表示第一遍wa70，查了好久没发现错误，后来发现N的范围不是20而是200表示当时电脑卡的屏幕有点……而且那个各位的0在下一行，__刚好卡的时候没有显示__……
其实可以说是裸的tarjan了

var n,sum,i,x,k,j:longint;bo:boolean;b:array[0..200,0..200]of boolean;
a:array[0..200]of boolean;
begin
readln(n);fillchar(b,sizeof(b),false);sum:=0; fillchar(a,sizeof(a),true); for i:=1 to n do begin read(x); while(x<>0)do begin b[i,x]:=true;read(x);end; end; for k:=1 to n do for i:=1 to n do for j:=1 to n do if i<>j then b[i,j]:=b[i,j]or(b[i,k]and b[k,j]); for i:=1 to n do if a[i] then begin for j:=1 to n do if(j<>i)and b[i,j]and b[j,i] then a[j]:=false; inc(sum);a[i]:=false; end; writeln(sum); end.

AC100纪念！！
强连通分量就可以了 顺带一提 这题和Victoria舞会3一样的代码

我蒟蒻来了，昨天仔细思考了一下，其实没问题的。
让众大神见笑了。

#include<stdio.h>
using namespace std;
long f[201][201],map[201][201],num[201],now[201],cnt,i,j,k,n;
void dfs(long k)
{
long go,i;
for (i=1;i<=num[k];i++)
{
go=map[k][i];
if (now[go]==0)
{
now[go]=cnt;
dfs(go);
}
}
}
int main()
{
scanf("%ld",&n);
for (i=1;i<=n;i++)
{
while (true)
{
scanf("%ld",&k);
if (k==0) break;
f[i][k]=true;
}
}
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if ((i!=k)&&(i!=j)&&(j!=k))
f[i][j]=f[i][j]||f[i][k]&&f[k][j];
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if ((i!=j)&&(f[i][j]!=f[j][i]))
{
f[i][j]=false;
f[j][i]=false;
}
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
if (f[i][j])
{
num[i]++;
map[i][num[i]]=j;
}
now[i]=0;
}
cnt=0;
for (i=1;i<=n;i++)
if (now[i]==0)
{
cnt++;now[i]=cnt;
dfs(i);
}
printf("%ld",cnt);
}
以上是我的AC代码，写得很传统。
但是我仍有点疑问。
如果A和B互相有好(已经染在一起），发现A与C也互相友好（在A的BFS中搜到了C）
那么C就直接染色。
但要不要判断B与C的关系了呢？我没有，但也过了。
仔细看下面大牛的代码，都没判断。
可能我哪里理解错了吧，望众大神指教。

BY 蒟蒻JSB 绍兴一中万岁！

评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 820 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 824 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 820 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 820 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 820 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 820 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 824 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 824 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 824 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 824 KiB, score = 10

Accepted, time = 0 ms, mem = 824 KiB, score = 100

代码

program P1022;
var n:integer;
a:array[1..200,1..200] of integer;
num:array[1..200] of integer;
flag:array[1..200] of boolean;
i,count:integer; m:integer;

procedure arrange(x:integer);
var i,j,target:integer;
begin
for i:=1 to num[x] do
if flag[a[x,i]] then
begin
target:=a[x,i];
for j:=1 to num[target] do
if a[target,j]=x then
begin
dec(m);
flag[x]:=false;
arrange(target);
break;
end;
end;
flag[x]:=false;
end;

begin
{assign(input,'P1022.in');
reset(input);
assign(output,'P1022.out');
rewrite(output);}
readln(n);
for i:=1 to n do
begin
count:=1;
read(a[i,count]);
while a[i,count]<>0 do
begin
inc(count);
read(a[i,count]);
end;
num[i]:=count-1;
end;

fillchar(flag,sizeof(flag),true);
for i:=1 to n do
if num[i]=0 then flag[i]:=false;

m:=n;
i:=1;
repeat
while not flag[i] do inc(i);
if i<=n then arrange(i);
until i>n;

writeln(m);
{close(input); close(output);}
end.