179 条题解

  • 3
    @ 2017-10-02 17:27:08

    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;
    }
    
  • 1
    @ 2019-05-17 14:12:00

    tarjan的注意,图的大小要开到n的平方,不然会炸(其实10000就够)

  • 1
    @ 2018-08-14 13:52:49
    #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;
    }
    
  • 1
    @ 2017-06-29 08:56:23

    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;
    }

  • 0
    @ 2019-01-29 20:52:36

    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;
    }

  • 0
    @ 2017-10-20 20:21:28

    一开始就以为是最简单的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;
    }

  • 0
    @ 2017-06-29 09:00:57

    老老实实用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;
    }

  • 0
    @ 2017-05-07 12:56:17
    /*
    问一下这题和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();
    }
    
    
  • 0
    @ 2017-04-20 22:02:44

    #

    状态

    耗时

    内存占用

    #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;
    }

  • 0
    @ 2017-03-08 00:03:49

    楼下许多代码其实是错的。。。
    反例:
    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;
    }
    
    
  • 0
    @ 2017-02-18 16:43:26

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

  • 0
    @ 2017-02-18 16:21:22

    #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;
    }
    并查集就可以了不用太复杂。

  • 0
    @ 2017-01-02 20:42:51

    #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;
    }

  • 0
    @ 2016-11-19 18:46:34

    1022 1023这两道题有毒啊

  • 0
    @ 2016-11-17 13:37:04

    强连通分量,很好的一道模板题
    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.

  • 0
    @ 2016-10-22 22:38:21

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

  • 0
    @ 2016-10-09 17:36:29

    编译成功

    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;
    }

  • 0
    @ 2016-08-20 10:55:40

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

    3
    2 0
    0
    2 0

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

  • 0
    @ 2016-08-13 09:37:37

    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.

  • 0
    @ 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.
    

信息

ID
1023
难度
4
分类
图结构 | 强连通分量 点击显示
标签
递交数
4310
已通过
1967
通过率
46%
被复制
11
上传者