Accepted

状态 耗时 内存占用

#1 Accepted 3ms 440.0 KiB
#2 Accepted 2ms 436.0 KiB
#3 Accepted 2ms 308.0 KiB
#4 Accepted 2ms 324.0 KiB
#5 Accepted 3ms 428.0 KiB
#6 Accepted 2ms 436.0 KiB
#7 Accepted 1ms 444.0 KiB
#8 Accepted 1ms 452.0 KiB
#9 Accepted 2ms 424.0 KiB
#10 Accepted 1ms 444.0 KiB

#include <bits/stdc++.h>
using namespace std;

const int maxn = 210;
int n, cmp[maxn];
bool vis[maxn];
vector<int> G[maxn], rG[maxn], vs;

void add_edge(int u, int v) {
    G[u].push_back(v);
    rG[v].push_back(u);
}

void dfs(int u) {
    vis[u] = true;
    for (int v : G[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
    vs.push_back(u);
}

void rdfs(int u) {
    vis[u] = true;
    for (int v : rG[u]) {
        if (!vis[v]) {
            dfs(v);
        }
    }
}

int kosaraju() {
    memset(vis, false, sizeof(vis));
    vs.clear();
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    memset(vis, false, sizeof(vis));
    int k = 0;
    for (int i = vs.size() - 1; i >= 0; i--) {
        if (!vis[vs[i]]) {
            k++;
            dfs(vs[i]);
        }
    }
    return k;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int u = 1, v; u <= n; u++) {
        while (cin >> v && v != 0) {
            add_edge(u, v);
        }
    }
    cout << kosaraju() << endl;
    return 0;
}

tarjan的注意，图的大小要开到n的平方，不然会炸（其实10000就够）

#include<bits/stdc++.h>
using namespace std;
const int maxn=204,maxm=40004;
int n,sum=0,dep=0,cnt=0;
int head[maxn],vis[maxn],dfn[maxn],low[maxn],col[maxn],in[maxn];
stack<int>s;
struct node{
    int to,next;
}e[maxm];
void add(int u,int v){
    e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
void tarjan(int u){
    vis[u]=1;
    dfn[u]=low[u]=++dep;
    s.push(u);
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[v],low[u]);
        }else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        col[u]==++sum;vis[u]=0;
        while(1){
            int x=s.top();
            s.pop();
            col[x]=sum;
            vis[x]=0;
            if(u==x) break;
        }
    }
}
void shrink_point(){
    for(int i=1;i<=n;i++){
        for(int j=head[i];j;j=e[j].next){
            int v=e[j].to;
            if(col[i]==col[v]) continue;
            in[col[v]]++;
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        while(cin>>x){
            if(x==0) break;
            add(i,x);
        }
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    shrink_point();
    int ans=0;
    for(int i=1;i<=sum;i++)
        if(!in[i]) ans++;
    cout<<ans;
}

一开始就以为是最简单的tarjian模板题，但是后来仔细读题发现并不是这样，问了同学，才A的。
大致就是强联通分量缩点之后，统计一遍入度为0的点，就是答案
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<string>
#define ll long long
#define inf 214748364
#define DB double
using namespace std;
inline int read()
{
int x=0,w=1;char ch=0;
while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*w;

}
int tot,n,h[10000],H[10000],totA;
struct po{
int u,v,c,last;
}a[10000],A[10000];
int ans;
int num[100000],T,dfn[10000],low[10000];
int q[10000],l,in[10000],to[100000];
int R[10000];
void add(int u,int v)
{
tot++;
a[tot].v=v;
a[tot].last=h[u];
h[u]=tot;
}
void Add(int u,int v)
{
totA++;
A[totA].v=v;
A[totA].last=H[u];
H[u]=totA;
}
void tarjian(int u)
{
dfn[u]=low[u]=++T;
in[u]=1;l++,q[l]=u;
for(int i=h[u];i;i=a[i].last)
{
int v=a[i].v;
if(!dfn[v])
{
tarjian(v);
low[u]=min(low[u],low[v]);

} else if(in[v]) low[u]=min(dfn[v],low[u]);
}
if(dfn[u]==low[u])
{
num[0]++;
do{
in[q[l]]=0;
to[q[l]]=num[0];
num[num[0]]++;
}while(q[l--]!=u);

}
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
int x;
while(scanf("%d",&x)!=EOF)
{
if(x==0) break;
add(i,x);
//add(x,i);

}

}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjian(i);
for(int i=1;i<=tot;i++)
{
int u=a[i].u;int v=a[i].v;
if(to[u]==to[v]) continue;
Add(to[u],to[v]);
R[to[v]]++;

}
for(int i=1;i<=num[0];i++)
{
if(R[i]==0) ans++;

}
printf("%d",ans);
return 0;
}

Accepted

状态 耗时 内存占用

#1 Accepted 3ms 360.0KiB
#2 Accepted 1ms 328.0KiB
#3 Accepted 3ms 384.0KiB
#4 Accepted 4ms 256.0KiB
#5 Accepted 3ms 200.0KiB
#6 Accepted 3ms 256.0KiB
#7 Accepted 3ms 256.0KiB
#8 Accepted 4ms 256.0KiB
#9 Accepted 1ms 332.0KiB
#10 Accepted 1ms 332.0KiB
本来想用一下简便方法，结果爆零，只好老老实实打了一遍Tarjan。
#include<cstdio>
#include<iostream>
using namespace std;
struct node{
int from,to,next;
}e[10010];
int v[250],book[250],dfn[250],low[250],s[250],father[250],rd[250],
flag[250],n,m,l,r,index=0,tot=0,top=0,ans=0,count=0,M=0;
void tarjan(int x){
book[x]=1;
s[++top]=x;
dfn[x]=low[x]=++index;
for(int j=v[x];j;j=e[j].next){
if(!book[e[j].to]){
tarjin(e[j].to);
if(low[x]>low[e[j].to])
low[x]=low[e[j].to];
}
else if(!flag[e[j].to])
if(low[x]>dfn[e[j].to])low[x]=dfn[e[j].to];
}

if(dfn[x]==low[x]){
count++;
while(s[top+1]!=x){
father[s[top]]=count;
flag[s[top--]]=1;
}
}
return;
}
void add_e(int x,int y){
e[++tot].from=x;
e[tot].to=y;
e[tot].next=v[x];
v[x]=tot;
return;
}
void in(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>m;
while(m!=0){
M++;
add_e(i,m);
cin>>m;
}
}
return;
}
int main(){
in();
for(int i=1;i<=n;i++)
if(!book[i])tarjan(i);
for(int i=1;i<=M;i++)
if(father[e[i].from]!=father[e[i].to])
rd[father[e[i].to]]++;
for(int i=1;i<=count;i++)
if(!rd[i])ans++;
cout<<ans;
return 0;
}

这题是DFS！不想粘代码了，记录一下思路就好。

开一个二维数组map[i,j],若i能通知j则map=1，否则，map=0

记录是否被访问过st[i]

记录父节点fa[i]

最后的统计nd[i]

先1到n扫一遍，若未访问过则:把i的父节点fa[i]设为i，并且search(i,i)，即从此点开始深搜

search（now，father）

先st[now]=1 //已访问过i

然后以now为出发点，查找i是否有未被访问的子枝

若有j，则fa[j]=father,继续search(j,father)

搜索完成后，把每个数的父节点保存在nd[i]中，即令nd[fa[i]]=1,再扫一遍nd中1的个数即可

简单地说这是一个不断搜索不断深入深入的过程，并且把每一个遇到的点的父节点都设为主干的那个。

include<bits/stdc++.h>

using namespace std;

struct{
int from,too,next;
}edge[40010];

int low[210],dfn[210],inwhich[210],head[210],Q[40010],rudu[210];

int ans,top,m,num;

bool flag[210],ru[210][210];

void add(int x,int y){
ans++;
edge[ans].from=x;
edge[ans].too=y;
edge[ans].next=head[x];
head[x]=ans;
}

void tarjan(int k){
num++;
dfn[k]=num;
low[k]=num;
flag[k]=true;
Q[++top]=k;
for (int i=head[k];i;i=edge[i].next){
int u=edge[i].too;
if (!dfn[u]){
tarjan(u);
low[k]=min(low[k],low[u]);
}
else{
if (flag[u]) low[k]=min(low[k],dfn[u]);
}
}
if (low[k]==dfn[k]){
inwhich[k]=++m;
flag[k]=false;
while(1){
int x=Q[top--];

inwhich[x]=m;
flag[x]=false;
if (k==x) break;
}
}
}

int main()
{
int n;
cin>>n;
int x;
for (int i=1;i<=n;i++){
int x;
cin>>x;
while (x!=0){
add(i,x);
cin>>x;
}
}
for (int i=1;i<=n;i++){
if (!dfn[i]) tarjan(i);
}
for (int i=1;i<=n;i++){
for (int j=head[i];j;j=edge[j].next){
int v=edge[j].too;
if (inwhich[v]==inwhich[i]) continue;
rudu[inwhich[v]]++;
}
}
int ansn=0;
for (int i=1;i<=m;i++)
if (rudu[i]==0) ansn++;
cout<<ansn;
return 0;
}

老老实实用Tarjan，很容易，一道很简单的模拟题，，，
#include<cstdio>
#include<iostream>
using namespace std;
int n,m,a,b,dfn[10001],low[10001],v[10001],shu=0,count=0,tot=0,vis[10001],s[10001],t=0,top=0,flag[10001],father[100001],ru[10001];
struct edge
{
int from,to,next;
}e[10001];
void add(int x,int y)
{
tot++;
e[tot].from=x;
e[tot].to=y;
e[tot].next=v[x];
v[x]=tot;
}
/*int find(int x)
{
if(father[x]!=x)return father[x]=find(father[x]);
return x;
}
void uni(int x,int y)
{
int r1=find(x),r2=find(y);
if(r1!=r2)father[r2]=r1;
}*/
void taj(int i)
{

dfn[i]=low[i]=++shu;
vis[i]=1;
s[++top]=i;
int j;
for(j=v[i];j;j=e[j].next)
{
int k=e[j].to;
if(!vis[k])
{
taj(k);
if(low[k]<low[i])low[i]=low[k];
}
else if(!flag[k])
{
if(low[i]>dfn[k])low[i]=dfn[k];
}
}
if(dfn[i]==low[i])
{
count++;
while(s[top+1]!=i)
{

flag[s[top]]=1;
father[s[top]]=count;
--top;

}
}

}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a;
if(a!=0)
add(i,a);
while(a!=0)
{
cin>>a;
if(a!=0)
add(i,a);
}

}
for(int i=1;i<=n;i++)
{
if(!dfn[i])taj(i);
}

for(int i=1;i<=tot;i++)
{

if(father[e[i].from]!=father[e[i].to])ru[father[e[i].to]]++;
}
for(int i=1;i<=count;i++)
{
if(ru[i]==0)t++;
}
cout<<t;
return 0;
}

/*
问一下这题和P1022有何区别
直接把题解搬过来了...OTZ
这题很明显是一个有向图模型~
同时是要求强连通分量的个数~！
因为n很小   所以完全可以用Floyd预处理
然后统计连通块
用并查集也很方便~
当然也可以写个标准一点的Tarjan统计SCC数量~
这里窝两个都写了一下
*/
/*
方法1:
Floyd判断连通性，最后注意统计连通块的方法：v数组
不再多说~
细节看代码就好
*/
/*#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cstdlib>
using namespace std;

bool a[203][203];
bool v[203];
int n;
int m;
int tot;

void init()
{
    int x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        while(scanf("%d",&x)==1&x)
            a[i][x]=1;
    }
}

void Floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(a[i][k]&&a[k][j])
                    a[i][j]=1;
}

void work()
{
    for(int i=1;i<=n;i++)
        if(!v[i])
        {
            for(int j=1;j<=n;j++)
                if(a[i][j]&&a[j][i]&&!v[j])
                    v[j]=1;
            tot++;
            v[i]=1;
        }
    cout<<tot<<endl;
}

int main()
{
    init();
    Floyd();
    work();
    return 0;
}
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

const int MAXN=205;
const int MAXM=40005;
struct Edge
{
    int to,next;
}e[MAXM];
int fisrt[MAXN];//Edges
int clock_cnt,scc_cnt;
int pre[MAXN],low[MAXN];
int sccno[MAXN];
stack<int> s;
int n,tot;

inline void Add_Edge(int& x,int& y)
{
    e[++tot].to=y;  e[tot].next=fisrt[x];   fisrt[x]=tot;
}

void init()
{
    memset(fisrt,-1,sizeof(fisrt));
    int v;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        while(scanf("%d",&v)==1&&v)
            Add_Edge(i,v);
    }
}

void dfs(int u)
{
    pre[u]=low[u]=++clock_cnt;
    s.push(u);
    for(int i=fisrt[u];i!=-1;i=e[i].next)
    {
        int& v=e[i].to;
        if(!pre[v])
        {
            dfs(v);
            low[u]=min(low[u],low[v]);
        }
        else    if(!sccno[v])
            low[u]=min(low[u],pre[v]);
    }
    if(low[u]==pre[u])
    {
        scc_cnt++;
        int x=0;
        for(;;)
        {
            x=s.top();  s.pop();
            sccno[x]=scc_cnt;
            if(x==u)
                break;
        }
    }
}

void Tarjan()
{
    for(int i=1;i<=n;i++)
        if(!pre[i])
            dfs(i);
    cout<<scc_cnt<<endl;
}

int main()
{
    init();
    Tarjan();
}

#

状态

耗时

内存占用

#1  Accepted  2ms 340.0KiB
#2  Accepted  2ms 324.0KiB
#3  Accepted  3ms 376.0KiB
#4  Accepted  3ms 340.0KiB
#5  Accepted  2ms 344.0KiB
#6  Accepted  2ms 320.0KiB
#7  Accepted  3ms 320.0KiB
#8  Accepted  2ms 320.0KiB
#9  Accepted  3ms 336.0KiB
#10  Accepted  2ms 320.0KiB

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=205;
int n,step=0,cnt=0,Head[maxn],Dfn[maxn],Lowlink[maxn],Stack[maxn],top=0,Instack[maxn],father[maxn],Belong[maxn],SCC=0,vst[maxn],ans=0,InDegree[maxn];
struct Edge {
int to,next;
} Edge[maxn*maxn];
void AddEdge(int from,int to) {
cnt++;
Edge[cnt].to=to;
Edge[cnt].next=Head[from];
Head[from]=cnt;
}
void Tarjan(int Now) {
step++;
Lowlink[Now]=Dfn[Now]=step;
Stack[++top]=Now;
Instack[Now]=1;
for(int i=Head[Now]; i; i=Edge[i].next) {
int Next=Edge[i].to;
if(!Dfn[Next]) {
Tarjan(Next);
Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);
} else if(Instack[Next])Lowlink[Now]=min(Lowlink[Now],Dfn[Next]);
}
if(Lowlink[Now]==Dfn[Now]) {
SCC++;
int y;
do {
y=Stack[top--];
Belong[y]=SCC;
Instack[y]=0;
} while(y!=Now);
}
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
int x;
while(x=Get_Int()) {
if(x==0)break;
AddEdge(i,x);
}
}
for(int i=1; i<=n; i++)if(!Dfn[i])Tarjan(i);
for(int i=1; i<=n; i++)
for(int j=Head[i]; j; j=Edge[j].next)
if(Belong[i]!=Belong[Edge[j].to])InDegree[Belong[Edge[j].to]]++;
for(int i=1; i<=SCC; i++)
if(InDegree[i]==0)ans++;
printf("%d\n",ans);
return 0;
}

楼下许多代码其实是错的。。。
反例：
5
2 0
3 0
4 0
5 0
0
Ans=1
正解：Tarjan建新图统计入度

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
    int num=0,bj=1;
    char x=getchar();
    while(x<'0'||x>'9') {
        if(x=='-')bj=-1;
        x=getchar();
    }
    while(x>='0'&&x<='9') {
        num=num*10+x-'0';
        x=getchar();
    }
    return num*bj;
}
const int maxn=205;
int n,step=0,cnt=0,Head[maxn],Dfn[maxn],Lowlink[maxn],Stack[maxn],top=0,Instack[maxn],father[maxn],Belong[maxn],SCC=0,vst[maxn],ans=0,InDegree[maxn];
struct Edge {
    int to,next;
} Edge[maxn*maxn];
void AddEdge(int from,int to) {
    cnt++;
    Edge[cnt].to=to;
    Edge[cnt].next=Head[from];
    Head[from]=cnt;
}
void Tarjan(int Now) {
    step++;
    Lowlink[Now]=Dfn[Now]=step;
    Stack[++top]=Now;
    Instack[Now]=1;
    for(int i=Head[Now]; i; i=Edge[i].next) {
        int Next=Edge[i].to;
        if(!Dfn[Next]) {
            Tarjan(Next);
            Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);
        } else if(Instack[Next])Lowlink[Now]=min(Lowlink[Now],Dfn[Next]);
    }
    if(Lowlink[Now]==Dfn[Now]) {
        SCC++;
        int y;
        do {
            y=Stack[top--];
            Belong[y]=SCC;
            Instack[y]=0;
        } while(y!=Now);
    }
}
int main() {
    n=Get_Int();
    for(int i=1; i<=n; i++) {
        int x;
        while(x=Get_Int()) {
            if(x==0)break;
            AddEdge(i,x);
        }
    }
    for(int i=1; i<=n; i++)if(!Dfn[i])Tarjan(i);
    for(int i=1; i<=n; i++)
        for(int j=Head[i]; j; j=Edge[j].next)
            if(Belong[i]!=Belong[Edge[j].to])InDegree[Belong[Edge[j].to]]++;
    for(int i=1; i<=SCC; i++)
        if(InDegree[i]==0)ans++;
    printf("%d\n",ans);
    return 0;
}

为什么在JDFZoj 上提交有7%错误这里就是accepted呢

#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std;
int n;
int point[10000];
int nex[10000],to[10000];
bool inloop[10000],noto[10000];
int ans=0;
void search(int n)
{
inloop[n]=false;
int side=point[n];
while(side!=0)
{
if(inloop[to[side]]==true)
search(to[side]);
side=nex[side];
}
}
int main()
{
memset(inloop,true,sizeof(inloop));
memset(point,0,sizeof(point));
memset(noto,true,sizeof(noto));
memset(nex,0,sizeof(nex));
cin>>n;
int m=0;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
while(x!=0)//输入第m条边 i到x
{
m++;
nex[m]=point[i];
point[i]=m;
to[m]=x;
noto[x]=false;
scanf("%d",&x);
}
}
for(int i=1;i<=n;i++)//讨论并查集的头结点
{
if(noto[i]==true)
{
ans++;
search(i);
}
}
for(int i=1;i<=n;i++)//讨论有循环的情况
{
if(inloop[i]==true)
{
ans++;
search(i);
}
}
cout<<ans<<endl;
return 0;
}
并查集就可以了不用太复杂。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define f(i,j,k) for(int i=k;i<=j;i++)
#define d(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
struct node {
int zhi,nex;
}e[400000+5];
int head[405];
int cnt;
int dfn[404];
int low [404],stac[404],instack[404];
int numbe,belong[404],bcnt;
int top;
void add(int x,int y)
{
cnt++;
e[cnt].nex=head[x];
e[cnt].zhi=y;
head[x]=cnt ;

}
void tarjan(int v) {
int u;
dfn[v] = low[v] = ++numbe;
instack[v] = true;
stac[++top] = v;
for (int i = head[v]; i ; i=e[i].nex) {
u = e[i].zhi;
if (!dfn[u]) {
tarjan(u);
if (low[u] < low[v])
low[v] = low[u];
}
else if (instack[u] && dfn[u] < low[v])
low[v] = dfn[u];
}
if (dfn[v] == low[v]) {
bcnt++;
do {
u = stac[top--];
instack[u] = false;
belong[u] = bcnt;
}
while (u != v);
}
}

bool se[404];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int m;
while(scanf("%d",&m)&&m)
{
add(i,m);
}
}
for(int i=1;i<=n;i++)
{
if(!belong[i])
tarjan(i);
}
int ans=0;

for(int i=1;i<=n;i++)
{
int p=belong[i];
if(!p) ans++;
else {
if(!se[p]) ans++,se[p]=true;
}
}
printf("%d",ans);
return 0;
}

1022 1023这两道题有毒啊

强连通分量，很好的一道模板题
pascal
//
var a:array[0..201,0..201] of longint;
f,v:array[0..201] of boolean;
stack,dfn,low:array[0..1000] of longint;
x,i,n,ans,deep,d:longint;
function min(x,y:longint):longint;
begin
if x<y then exit(x)
else exit(y);
end;
procedure dfs(x:longint);
var i:integer;
begin
inc(d);
low[x] := d;
dfn[x] := d;
f[x] := true;
inc(deep);
stack[deep] := x;
for i := 1 to a[x,0] do
if not(v[a[x,i]]) then
begin
v[a[x,i]]:= true;
dfs(a[x,i]);
low[x] := min(low[x],low[a[x,i]]);
end
else if f[a[x,i]] then
low[x] := min(low[x],dfn[a[x,i]]);
if dfn[x]=low[x] then
inc(ans);
while stack[deep+1]<>x do
begin
f[stack[deep]] := false;
dec(deep);
end;
end;
begin
readln(n);
d := 0;
fillchar(a,sizeof(a),0);
for i := 1 to n do
begin
read(x);
while x <> 0 do
begin
inc(rudu[x]);
inc(a[i,0]);
a[i,a[i,0]] := x;
read(x);
end;
end;
for i := 1 to n do
low[i] := i;
for i := 1 to n do
if not(v[i]) then
begin
v[i] := true;
dfs(i);
end;
writeln(ans);
end.


和2一样的啊。。。水水的并查集ac

编译成功

foo.cpp: In function 'void cal()':
foo.cpp:55:6: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
int flag=0;
^

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

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

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

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

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

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

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

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

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

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

Accepted, time = 45 ms, mem = 59288 KiB, score = 100

代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
int const MAXN=1000000;
int vis[MAXN],mark[MAXN],ss[MAXN],cnt,in[MAXN],Tree[MAXN];
int m,n,head1[MAXN],head2[MAXN],num_edge1,num_edge2,num[MAXN],tree_n[MAXN],ans;
struct EDGE{
int next,to,val;
}edge1[MAXN],edge2[MAXN];
void Add_edge(int from,int to){
edge1[++num_edge1].next=head1[from];
edge1[num_edge1].to=to;
head1[from]=num_edge1;
}
void Add_edge2(int from,int to){
edge2[++num_edge2].next=head2[from];
edge2[num_edge2].to=to;
head2[from]=num_edge2;
}
void DFS1(int s){
mark[s]=1;
for (int i=head1[s];i!=0;i=edge1[i].next){
int v=edge1[i].to;
if(!mark[v]){
DFS1(v);
}
}
ss[++ss[0]]=s;

}
void DFS2(int s){
num[s]=cnt;
++tree_n[cnt];
mark[s]=1;
for (int i=head2[s];i!=0;i=edge2[i].next){
int v=edge2[i].to;
if(!mark[v]){
DFS2(v);
}
}
}
void cal(){
memset(mark,0,sizeof(mark));
for (int i=1;i<=n;i++){
for (int j=head1[i];j!=0;j=edge1[j].next){
int v=edge1[j].to;
if(num[i]!=num[v])
mark[num[i]]=1;
}
}
int flag=0;
for (int i=1;i<=cnt;i++){
if(!mark[i]){
flag=i;ans++;
}
}
//if(ans==1) cout<<tree_n[flag];
//else cout<<'0'
cout<<ans;
}
int main(){
//freopen("kos.in","r",stdin);
scanf("%d",&n);
for (int i=1;i<=n;i++){int a;
while(scanf("%d",&a)&&a){
Add_edge(i,a); //cout<<i<<' '<<a<<endl;
Add_edge2(a,i);
}
}
for (int i=1;i<=n;i++){
if(!mark[i])
DFS1(i);
}
memset(mark,0,sizeof(mark));
for (int i=ss[0];i>0;i--){
if(!mark[ss[i]]) {
cnt++;
DFS2(ss[i]);
}
}
cal();
return 0;
}

真心感觉数据是错的2333
并查集解法的反例：

3
2 0
0
2 0

实际答案应为2，但并查集输出1
所以我写了一个卡时搜索，结果0
RP-------

var p:array[1..1000,1..1000]of boolean;
dfn,low,f:array[1..1000]of longint;
s,ss:array[1..1000]of boolean;
n,i,b,h,t,ans:longint;
function min(a,b:longint):longint;
begin
if a>b then exit(b)
else exit(a);
end;
procedure tarjan(x:longint);
var i,j,k:longint;
begin
inc(h);
dfn[x]:=h;low[x]:=h;
inc(t); f[t]:=x;
s[x]:=true;ss[x]:=true;
for i:=1 to 200 do
if p[x,i] then
begin
if not s[i] then
begin
tarjan(i);
low[x]:=min(low[x],low[i]);
end
else if ss[i] then low[x]:=min(low[x],dfn[i]);
end;
if dfn[x]=low[x] then
begin
inc(ans);
while f[t+1]<>x do
begin
ss[f[t]]:=false;
dec(t);
end;
end;
end;
begin
readln(n);
for i:=1 to n do
begin
while true do
begin
read(b);
if b=0 then break;
p[b,i]:=true;p[i,b]:=true;
end;
end;
for i:=1 to n do low[i]:=i;
for i:=1 to n do
if not s[i] then tarjan(i);
writeln(ans);
end.