题解 - Vijos

0

浮光过客 LV 10 @ 2016-08-01 19:53:28

program vijos1023;
var
  ans,b,c,t,n,i,j,k,l:longint;
  a,a2,a3:array[0..1000,0..2] of longint;
  o2,o3,zhan,kind,o,low,dfn:array[0..1000] of longint;
  top,cc,now,tot,pop,tot2,tot3:longint;
  f,inz:array[0..1000] of boolean;
  function min(a,b:longint):longint;
    begin
      if a<b then exit(a) else exit(b);
    end;
  procedure addedge2(p,q:longint);
    begin
      inc(tot2);
      a2[tot2,1]:=q;
      a2[tot2,0]:=o2[p];
      o2[p]:=tot2;
    end;
  procedure addedge3(p,q:longint);
    begin
      inc(tot3);
      f[q]:=false;
      a3[tot3,1]:=q;
      a3[tot3,0]:=o3[p];
      o3[p]:=tot3;
    end;
  procedure addedge(p,q:longint);
    begin
      inc(tot);
      a[tot,1]:=q;
      a[tot,0]:=o[p];
      o[p]:=tot;
    end;
  procedure init;
    begin
      readln(n);
      tot:=0;
      tot2:=0;
      tot3:=0;
      ans:=0;
      cc:=0;
      pop:=0;
      top:=0;
      fillchar(inz,sizeof(inz),false);
      fillchar(f,sizeof(f),true);
      fillchar(dfn,sizeof(dfn),0);
      for i:=1 to n do
        begin
        while true do
          begin
            read(b);
            if b=0 then break;
            addedge(i,b);
          end;
        readln;
        end;
    end;
  procedure dfs(x:longint);
    var
      t,now:longint;
    begin
      inc(cc);
      low[x]:=cc;
      dfn[x]:=cc;
      inc(top);
      zhan[top]:=x;
      inz[x]:=true;
      t:=o[x];
      while (t<>0) do
        begin
          if (dfn[a[t,1]]=0)then
            begin
              dfs(a[t,1]);
              low[x]:=min(low[x],low[a[t,1]]);
            end
          else
            if inz[a[t,1]] then
              low[x]:=min(low[x],low[a[t,1]]);
          t:=a[t,0];
        end;
      if (dfn[x]=low[x]) then
         begin
           inc(pop);
           while (zhan[top]<>x) do
             begin
               now:=zhan[top];
               kind[now]:=pop;
               inz[zhan[top]]:=false;
               dec(top);
               addedge2(pop,now);
             end;
           now:=zhan[top];
           inz[zhan[top]]:=false;
           top:=top-1;
           kind[now]:=pop;
           addedge2(pop,now);
         end;
      end;
  procedure tarjan;
    var
      i,t:longint;
    begin
      for i:=1 to  n do
        begin
          if (dfn[i]=0) then dfs(i);
        end;
      for i:=1 to n do
        begin
          t:=o[i];
          while t<>0 do
            begin
              if (kind[i]<>kind[a[t,1]])   then
                begin
                  addedge3(kind[i],kind[a[t,1]]);
                end;
              t:=a[t,0];
            end;
        end;
    end;
  procedure serch;
    begin
      for i:=1 to pop do
        begin
          if f[i] then inc(ans);
        end;
      writeln(anns);
    end;
begin
  init;
  tarjan;
  serch;
end.

0

Okami LV 8 @ 2016-07-24 11:00:33

并查集建森林，将该人能通知到的人的父亲设为该人，最后统计树的个数即为答案。

#include<iostream>
#include<cstring>
using namespace std;
int f[1000];
int find(int x){
    if(f[x] == x)return x;
    f[x] = find(f[x]);
    return f[x]; 
}
void merge(int x,int y){
    int f1 = find(x);
    int f2 = find(y);
    f[f1] = f2;
}
int main(){
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++)f[i] = i;
    for(int i = 1;i<=n;i++){
        int t;
        cin>>t;
        while(t!=0){
            merge(t,i);
            cin>>t;
        }
    }
    bool father[1000];
    memset(father,0,sizeof(father));
    for(int i = 1;i<=n;i++){
        father[find(i)] = 1;
    }
    int ans = 0;
    for(int i = 1;i<=n;i++)if(father[i])ans++;
    cout<<ans<<endl;
    return 0;
}

0

ojplayer LV 5 @ 2016-06-13 12:50:13


#include <iostream>
#include <queue>
using namespace std;
typedef struct Edge
{
    int adj;
    Edge * next;
} Edge;
typedef struct Vetex
{
    int inc;
    Edge * first;
}Vetex;
int main()
{
    int n ;
    cin >> n;
    int * vs = new int[n+1];
    Vetex * v = new Vetex[n+1];
    for(int i = 0; i <=n; ++i)
    {
        vs[i] = 0;
        v[i].inc = 0;
        v[i].first = 0;
    }
    Edge * e = 0;
    int nd;
    for(int i = 1; i <=n ; ++i)
    {
        while(cin >>nd && nd )
        {
            e = new Edge;
            e->adj = nd;
            e->next = v[i].first;
            v[i].first = e;
            ++v[nd].inc;
        }
    }
    queue<int> q;
    int temp,count = 0;
    bool loop;
    for(int i = 1; i <=n ;i++)
    {
        if(!vs[i])
        {
            loop = false;
            q.push(i);
            while(!q.empty())
            {
                temp = q.front();
                q.pop();
                vs[temp] = 1;
                e = v[temp].first;
                while(e)
                {
                    if(e->adj==i)
                    {
                        loop = true;
                    }
                    else if(!vs[e->adj])
                    {
                        q.push(e->adj);
                    }
                    e = e->next;
                }
            }
            if(loop || !v[i].inc)
            {
                ++count;
            }
        }
    }
    cout << count;
    delete[] vs;
    delete[] v;
    vs = 0;
    v = 0;
    return 0;
}

0

无·心 LV 8 @ 2016-03-13 11:19:34

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 556 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 = 15 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 = 556 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 556 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 560 KiB, score = 10
Accepted, time = 15 ms, mem = 560 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;
}

0

核糖核酸 LV 8 @ 2016-01-28 11:59:55

DFS大法好，
哈哈哈哈哈！！！

0

核糖核酸 LV 8 @ 2016-01-28 11:59:11

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
bool map[210][210];
bool b[210];
bool v[210];
int set[210];
int ans,n,i,u,root;

void dfs(int p)
{
int j;
set[p]=root;
for(j=1; j<=n; j++)
if(j!=p)
{
if(v[j]==true && map[p][j]==true)
{
//printf("从%d传到%d\n", p, j);
v[j]=false;
dfs(j);
}
}
}

int main()
{
scanf("%d", &n);
for(i=1; i<=n; i++)
for(u=1; u<=n; u++)
map[i][u]=false;
for(i=1; i<=n; i++)
{
scanf("%d", &u);
while(u!=0)
{
map[i][u]=true;
scanf("%d", &u);
}
}

for(i=1; i<=n; i++) set[i]=i;

for(i=1; i<=n; i++)
if(i==set[i])
{
memset(v,true,sizeof(v));
root=set[i];
dfs(i);
}
for(i=1; i<=n; i++) b[i]=false;
ans=0;
for(i=1; i<=n; i++)
if(b[set[i]]==false)
{
ans++;
b[set[i]]=true;
}
printf("%d", ans);
return 0;
}

0

核糖核酸 LV 8 @ 2016-01-28 11:58:12

DFS秒过啊，用神么**Tarjan**，**并查集**。

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

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

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

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

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

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

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

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

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

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

Accepted, time = 22 ms, mem = 320 KiB, score = 100

0

浮光过客 LV 10 @ 2015-10-13 11:25:21

tarjan算法

编译成功

Free Pascal Compiler version 2.6.4 [2014/03/06] for i386
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(3,9) Note: Local variable "c" not used
foo.pas(3,11) Note: Local variable "t" not used
foo.pas(3,17) Note: Local variable "j" not used
foo.pas(3,19) Note: Local variable "k" not used
foo.pas(3,21) Note: Local variable "l" not used
foo.pas(4,5) Note: Local variable "a2" is assigned but never used
foo.pas(4,8) Note: Local variable "a3" is assigned but never used
foo.pas(6,10) Note: Local variable "now" not used
Linking foo.exe
132 lines compiled, 0.1 sec , 29104 bytes code, 1628 bytes data
8 note(s) issued
测试数据 #0: Accepted, time = 10 ms, mem = 824 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 828 KiB, score = 10
测试数据 #2: Accepted, time = 10 ms, mem = 828 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 832 KiB, score = 10
测试数据 #4: Accepted, time = 1 ms, mem = 828 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 828 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 828 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 828 KiB, score = 10
测试数据 #8: Accepted, time = 2 ms, mem = 828 KiB, score = 10
测试数据 #9: Accepted, time = 4 ms, mem = 832 KiB, score = 10
Accepted, time = 57 ms, mem = 832 KiB, score = 100
代码
program vijos1023;
var
ans,b,c,t,n,i,j,k,l:longint;
a,a2,a3:array[0..1000,0..2] of longint;
o2,o3,zhan,kind,o,low,dfn:array[0..1000] of longint;
top,cc,now,tot,pop,tot2,tot3:longint;
f,inz:array[0..1000] of boolean;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure addedge2(p,q:longint);
begin
inc(tot2);
a2[tot2,1]:=q;
a2[tot2,0]:=o2[p];
o2[p]:=tot2;
end;
procedure addedge3(p,q:longint);
begin
inc(tot3);
f[q]:=false;
a3[tot3,1]:=q;
a3[tot3,0]:=o3[p];
o3[p]:=tot3;
end;
procedure addedge(p,q:longint);
begin
inc(tot);
a[tot,1]:=q;
a[tot,0]:=o[p];
o[p]:=tot;
end;
procedure init;
begin
readln(n);
tot:=0;
tot2:=0;
tot3:=0;
ans:=0;
cc:=0;
pop:=0;
top:=0;
fillchar(inz,sizeof(inz),false);
fillchar(f,sizeof(f),true);
fillchar(dfn,sizeof(dfn),0);
for i:=1 to n do
begin
while true do
begin
read(b);
if b=0 then break;
addedge(i,b);
end;
readln;
end;
end;
procedure dfs(x:longint);
var
t,now:longint;
begin
inc(cc);
low[x]:=cc;
dfn[x]:=cc;
inc(top);
zhan[top]:=x;
inz[x]:=true;
t:=o[x];
while (t<>0) do
begin
if (dfn[a[t,1]]=0)then
begin
dfs(a[t,1]);
low[x]:=min(low[x],low[a[t,1]]);
end
else
if inz[a[t,1]] then
low[x]:=min(low[x],low[a[t,1]]);
t:=a[t,0];
end;
if (dfn[x]=low[x]) then
begin
inc(pop);
while (zhan[top]<>x) do
begin
now:=zhan[top];
kind[now]:=pop;
inz[zhan[top]]:=false;
dec(top);
addedge2(pop,now);
end;tarjan算法
now:=zhan[top];
inz[zhan[top]]:=false;
top:=top-1;
kind[now]:=pop;
addedge2(pop,now);
end;
end;
procedure tarjan;
var
i,t:longint;
begin
for i:=1 to n do
begin
if (dfn[i]=0) then dfs(i);
end;
for i:=1 to n do
begin
t:=o[i];
while t<>0 do
begin
if (kind[i]<>kind[a[t,1]]) then
begin
addedge3(kind[i],kind[a[t,1]]);
end;
t:=a[t,0];
end;
end;
end;
procedure serch;
begin
for i:=1 to pop do
begin
if f[i] then inc(ans);
end;
writeln(ans);
end;
begin
init;
tarjan;
serch;
end.

0

zhouyis LV 8 @ 2015-08-28 13:22:25

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

0

1464942666 LV 8 @ 2015-08-08 21:12:41

并查集妥妥的...
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int n, ans = 0;
int father[10001];

void read(int &x) {
char chr = getchar();
x = 0;
while (chr < '0' || x > '9')
chr = getchar();
while (chr <= '9' && chr >= '0') {
x *= 10; x += chr - 48;
chr = getchar();
}
}

int find(int x) {
int root;
if (father[x] == x)
return x;
else
root = find(father[x]);
return father[x] = root ;
}

void union_set(int u, int v) {
int fu = find(u), fv = find(v);
if (fu != fv)
father[fv] = fu;
}

int main() {
//freopen("input.txt","r",stdin);
cin >> n;
for (int i = 1; i <= n; i++)
father[i] = i;
for (int i = 1; i <= n; i++) {
int x;
read(x);
while (x) {
union_set(i, x);
read(x);
}
}
for (int i = 1; i <= n; i++) {
if (father[i] == i)
ans++;
}
cout << ans << endl;
//fclose(stdin);
return 0;
}

0

2859198007 LV 8 @ 2015-04-23 18:25:46

题目的意思好像与题意不符合，假设有这么一组数据：
5
2 0
3 4 0
0
0
4 0
画图明显答案是2
但按照AC程序走却是1，数据理解为A通知B相当于B也能通知A
应该这么写：
include<iostream> include<cstdio> include<cstdlib>
using namespace std;
int N,tot;
int fa[300000];
int vis[300000];
int fin(int x){
if(x!=fa[x]) fa[x]=fin(fa[x]);
return fa[x];
}
int main(){
scanf("%d",&N);
for(int k=1;k<=N;k++){
fa[k]=k;
}

for(int i=1;i<=N;i++){
for(int j=1,x;j<=N+1;j++){
scanf("%d",&x);
if(x==0) break;
else{
if(vis[x]==0){
int r1=fin(i);
int r2=fin(x);
fa[r2]=r1;
vis[x]=1;
}
}
}
}
for(int p=1;p<=N;p++){
if(fa[p]==p){
tot++;
}
}
cout<<tot;
return 0;
}

0

huanghongxun LV 10 @ 2014-08-12 18:57:48

并查集不错。。

Block Code

#include <cstdio>
int p[10005],k=0,n,i,x;
int find(int x) { return p[x]==x?x:p[x]=find(p[x]); }
int main() {
scanf("%d",&n);
for(i=1;i<=n;i++) p[i]=i;
for(i=1;i<=n;i++) for(;;) {
scanf("%d",&x); if(!x) break;
p[find(x)]=p[find(i)];
}
for(i=1;i<=n;i++) if(p[i]==i) k++;
printf("%d",k);
return 0;
}

0

醉江楼 LV 8 @ 2014-05-20 22:27:54

哎，范围看错了。。。。

0

juan1973 LV 10 @ 2014-02-07 12:43:38

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

0

juan1973 LV 10 @ 2014-02-06 21:01:39

#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

ws_ypl LV 8 @ 2013-10-15 21:37:57

楼下理论上是错的。

0

口香糖万岁 LV 8 @ 2013-07-30 21:41:14

program p1023;
var i,n,x,k,j:longint;
f:array[1..5000] of longint;
function find(a:longint):longint;
begin
if f[a]=a then exit(a);
f[a]:=find(f[a]);
exit(f[a]);
end;

begin
assign(input,'p1023.in');
reset(input);
assign(output,'p1023.out');
rewrite(output);
readln(n);
for i:=1 to n do
f[i]:=i;

for i:=1 to n do
for j:=1 to 200 do
begin
read(x);
if x=0 then break;
f[find(x)]:=find(i);
end;

for i:=1 to n do
if f[i]=i then inc(k);
write(k);
end.
楼下貌似有些复杂 - -

0

SEX丶Elope LV 6 @ 2013-02-16 10:13:27

点击查看程序源码+详细题解

0

dmcgow LV 8 @ 2012-08-14 19:51:45

数据有问题.

明显两题不一样..

0

MyLove LV 8 @ 2012-08-08 17:18:35

理论上和P1022是不同的，一个判一边，一个判两边。但是VIJOS脑子不太好，数据放错了……P1022是P1023的，P1023的还是P1023的，所以两题一个程序全部AC

题解

179 条题解

Block Code

Victoria的舞会3

信息

状态

开发

支持

题解

179 条题解

Block Code

Victoria的舞会3

信息

状态

开发

支持

还没有账户？

登录