并查集肯定过不了,不要试了(详情参见第二篇题解)
by Strong_Jelly @ 2019-05-06 15:17:09
@[littleseven](/space/show?uid=144702)
by Strong_Jelly @ 2019-05-06 15:17:12
@[神兵qqq1112](/space/show?uid=143681)
为啥呢大佬求解
by littleseven @ 2019-05-07 12:41:22
@[littleseven](/space/show?uid=144702)
1.亲身体验
2.因为并查集是双向的。
就比如说:
有五个点1,2,3,4,5;1,2,3,4,5;
11给22拷贝,
22给4,54,5拷贝,
33给44拷贝,
4,54,5不给别人。
那么我们就会发现了,33的父亲会变成1,1,
然后程序就会输出11,就愉快的WAWA了!
by Strong_Jelly @ 2019-05-07 12:44:20
```cpp
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
int n, fa[100001], x, ans;
bool f[1001][1001];
void floy()
{
for(int k = 1; k <= n; k++)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(f[i][k] && f[k][j])
{
f[i][j] = true;
}
}
}
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
fa[i] = i;
}
for(int i = 1; i <= n; i++)
{
while(cin>>x && x)
{
f[i][x] = true;
}
}
floy();
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(f[i][j])
{
fa[j] = fa[i];
}
}
}
for(int i = 1; i <= n; i++)
{
if(fa[i] == i)
{
ans++;
}
}
printf("%d", ans);
return 0;
}
```
floyed能过
by Strong_Jelly @ 2019-05-07 12:45:39