麻烦看清楚~不是最小点基

是求强连通分量

非常典型的并查集,我写了20多行一遍就过

最小点基

基础阿！

求最高强连通分支的个数，其实就是求最小点基.一次AC

1、对图G进行dfs，记下每个结点变黑(已检查完毕)的时间顺序,注意,不是变灰的时间.

2、将图G的所有边反向,构造图Gr.

3、用从后往前的时间顺序,dfs图Gr.

4、得到的森林中每棵树对应一个强连通分量.

有人在吗，很急，指点一下啊，感激不尽！

这个题目的描述应该有问题吧~~郁郁~~哪位大牛帮忙解释一下~~

很简单啊,一次AC. SPEAKER

求最高强连通分支的个数，其实就是求最小点基，和1023的一模一样。

很简单啊,一次AC.

求最高强连通分支的个数，其实就是求最小点基，和1023的一模一样。

呵呵，我也是COPY了一下1023的，就AC了

用笨点的办法也可以过!!!!遍历图,看多少次可以把所有结点全都访问完.

当然不能递归啦,,不然栈溢出!

和克鲁斯卡尔最小生成树的思路好像差不多

我和000有相同的经历

真不知道这两个题为什么用相同的程序能过

我把1023的题解放这里居然通过了

/*
这题很明显是一个有向图模型~
同时是要求强连通分量的个数~！
因为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();
}

#include<bits/stdc++.h>
using namespace std;
bool f[201][201];
int n,i,j,ans,fa[201],sum[201];
int father(int x) {
    int r=x;
    while (r!=fa[x]) {
        r=fa[x];
        fa[x]=father(r);
    }
    return fa[x];
}
int uni(int x,int y) {
    int f1=father(x),f2=father(y);
    fa[f2]=f1;
}
int main() {
    cin>>n;
    for (i=1; i<=n; i++) {
        int x=i;
        while (x!=0) {
            f[i][x]=1;
            cin>>x;
        }
        fa[i]=i;
    }
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
            if (f[i][j]&&f[j][i]&&father(i)!=father(j))
                uni(i,j);
    for (i=1; i<=n; i++)
        fa[i]=father(i);
    for (i=1; i<=n; i++)
        sum[fa[i]]++;
    for (i=1; i<=n; i++)
        if (sum[i]>0) ans++;
    cout<<ans<<endl;
}

水水的并查集。。。然而数据是200而不是20。。。这是个坑。。。我就被坑死一次啊！！！

这么水的题，随便怎么解都行的（只要方案可行）。
并查集：
pascal
var n,i,x,a,b:longint;
fa:array[1..21]of longint;
function dad(x:longint):longint;
begin
if fa[x]=x then dad:=x else
dad:=dad(fa[x]);
fa[x]:=dad;
end;
begin
readln(n);
for i:=1 to n do fa[i]:=i;
for i:=1 to n do
begin
read(x);
while x<>0 do
begin
a:=dad(x);
b:=dad(i);
if a<>b then fa[a]:=fa[b];
read(x);
end;
end;
a:=0;
for i:=1 to n do
if dad(i)=i then inc(a);
writeln(a);
end.


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

#include<cstdio>
#include<cstring>
int fa[205];
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void Union(int a,int b)
{
if(find(a)!=find(b))
{
fa[find(a)]=find(b);
}
}
int main()
{
int n,i,j,k,p=0,count=0;
scanf("%d",&n);
k=n;
for(i=1;i<=n;i++) fa[i]=i;
for(i=1;i<=n;i++)
{
int x;
while(scanf("%d",&x))
{
if(x==0) break;
Union(i,x);
}
}
for(i=1;i<=n;i++)
{
k--;
p=0;
for(j=i+1;j<=n;j++) if(find(i)==find(j)) k--,p=1;
if(p) count++;
}
n-=count;
printf("%d",n);
return 0;
}