...把P1022的并查集甩过来就AC了

这道题是求极大连通子图，1022是求最小点基，1022的数据显然太弱了，用求极大连通子图的算法竟然能过

可以递归的啊~~~还是0ms呢....

其实弱题一道

其实此题很弱。。。。。。

DFS即可

先从搜索入度为0的点，将它所有能到达的点都标记上。然后在从没有标记的点开始搜索，把所有能到达的点也标记上，直到所有点都已标记上。

1、先用FLOYED预处理，求出谁能通知道谁

2、统计那些谁也通知不到的人，然后标记她能通知到的人。

3、剩下的未标记的点一定是属于环中的点，统计环的个数就行了。我的方法是枚举枚个点，然后标记和每个点相关的点。

看了各位大牛的题解．．

终于第一次知道了最小点基

也知道了求最小点基数的正确方法．．

这题目都怎么出的阿

最小点基和强连通分量明明不是完全相同的

可是我也是1022和1023用同一个程序过的。

是不是懒得出数据啊。

先做P1022再做本题

图论中的最小点基~~~~~

简单的

很基础呀~~~~~

这种题也是难度3?同意我的举手

哈哈，果然。1022和1023一模一样

用递归做，最多200层，怎么会溢出呢？

怎么和前一题一样...就是换了个说法...

不过我用递归似乎栈没有溢出.

广度遍历或宽度遍历.几次遍历完答案就是几.

(看来不能递归,否则就像我这样)

编译通过...

├ 测试数据 01：运行时错误...| 错误号: 202 | 堆栈溢出错

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 04：运行时错误...| 错误号: 202 | 堆栈溢出错

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：运行时错误...| 错误号: 202 | 堆栈溢出错

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：运行时错误...| 错误号: 202 | 堆栈溢出错

├ 测试数据 10：运行时错误...| 错误号: 202 | 堆栈溢出错

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：40 有效耗时：0ms

递归把栈撑爆....

咋的 和p1022一样的 题目啊。。。

直接用双向图,看多少次便历完.

就是极大连通子图问题

1022＆1023我用的1个程序过的

先求出入度为0的点的个数，然后求出环的个数，结果就是二者之和。

代码真的不长...

#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cstring>
#include <iostream>
#include <algorithm>
#define QU queue
#define ST stack
#define VC vector
#define PQ priority_queue
#define IT int
#define CR char
#define VD void
#define BL bool
#define LL long long
#define LINF (1LL<<60)
#define INF (0x3f3f3f3f)
#define IOS ios::sync_with_stdio(0)
#define F(x, y, z) for(int x=y; x<=z; x++)
#define D(x, y, z) for(int x=z; x>=y; x--)
#define MM(x, y) memset(x, y, sizeof(x))
#define PB push_back
#define GC getchar
#define LE length
#define PF printf
#define SF scanf
#define FT front
#define CL clear
#define EM empty
#define SZ size
#define PT puts
#define PS push
#define MX max
#define MI min
#define PP pop
#define TP top
using namespace std;
#define N (200)
ST<IT> st;
VC<IT> e[N+5],e1[N+5];
IT n,ct,ct1,ans,in[N+5],vs[N+5],dfn[N+5],low[N+5],bel[N+5];
VD TJ (IT t)
{
    IT x;
    st.PS(t),vs[t]=1,dfn[t]=low[t]=++ct;
    F(i,0,(IT)e[t].SZ()-1)
    {
        x=e[t][i];
        if (!dfn[x]) TJ(x),low[t]=MI(low[t],low[x]);
        else if (vs[x]) low[t]=MI(low[t],dfn[x]);
    }
    if (dfn[t]==low[t])
    {
        vs[t]=0,bel[t]=++ct1;
        while(st.TP()!=t) bel[st.TP()]=ct1,vs[st.TP()]=0,st.PP();
        st.PP();
    }
}
IT main ()
{
    IT x;
    SF("%d",&n);
    F(i,1,n) while(SF("%d",&x)&&x!=0) e[i].PB(x);
    F(i,1,n) if (!dfn[i]) TJ(i);
    F(i,1,n) F(j,0,(IT)e[i].SZ()-1)
    {
        x=e[i][j];
        if (bel[i]!=bel[x]) e1[bel[i]].PB(bel[x]),in[bel[x]]++;
    }
    F(i,1,ct1) if (!in[i]) ans++;
    PF("%d\n",ans);
    return 0;
}

并查集，就是6！
思路是把第i人作为他能通知到的来宾的祖先，最后统计有几个森林就行
其实这题和1022的方法可以通用。。
c++
#include<iostream>
#include <cstdio>
using namespace std;
int f[201], n, ans=0;
int getf(int v){
if(f[v]==v) return v;
else{
f[v]=getf(f[v]);
return f[v];
}
}
void merge(int v, int u){
int t1, t2;
t1=getf(v);
t2=getf(u);
if(t1!=t2)
f[t2]=t1;
}
int main(){
int i, t;
scanf("%d",&n);
for(i=1; i<=n; i++) f[i]=i;
for(i=1; i<=n; i++)
while (true){
scanf("%d",&t);
if (t==0) break;
merge(i, t);
}
for (i=1;i <=n;i++) if (f[i]==i) ans++;
printf("%d",ans);
}