orz加强数据吧
查看原帖
orz加强数据吧
60299
Patrickpwq楼主2018/6/14 16:10
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

inline int read()
{
    int i=0;char c;bool z=false;
    while(isspace(c=getchar()));
    if(c=='-')	z=true,c=getchar();
    while(isdigit(c)) i=i*10+c-'0',c=getchar();
    if(!z)	return i;
    else return -i;
}

int n,m,tot,sign,top,sum;
int to[50005],first[10005],next[50005]; 
int dfn[10005],low[10005];
int sta[10005];
int belong[10005];
bool insta[10005];

int out[10005];
int num[10005];
void add(int x,int y)
{
    tot++;
    next[tot]=first[x];
    to[tot]=y;
    first[x]=tot;
}

void dfs(int x)
{
    int i;
    sign++;
    dfn[x]=sign,low[x]=sign;
    sta[++top]=x;
    insta[x]=true;
    int k=first[x];
    while(k!=0)
    {
        i=to[k];
        if(dfn[i]==0)
        {
            dfs(i);
            if(low[i]<low[x])	low[x]=low[i];
        }
        else
        {
            if(insta[i]==true&&dfn[i]<low[x])	low[x]=dfn[i];
        }
        k=next[k];
    }
    
    if(low[x]==dfn[x])
    {
        sum++;
        i=sta[top];
        while(i!=x)
        {
            belong[i]=sum;
            insta[i]=false;
            top--;
            i=sta[top];
        }
        top--;
        insta[top]=false;
        belong[i]=sum;
    }
} 
int main()
{
    while(cin>>n>>m)
    {
    
    for(int i=1;i<=m;i++)
    {
        int x,y;
        x=read();
        y=read();
        add(x,y);		
    }
    for(int i=1;i<=n;i++)
    {
        if(dfn[i]==0) dfs(i);
    }
    
    
    for(int i=1;i<=n;i++)
    {
        int tmp=belong[i];
        num[tmp]++;
        for(int j=first[i];j;j=next[j])
        {
            int en=to[j];
            if(belong[i]!=belong[en])
            {
                out[tmp]++;
            }
        }
    }
    
    int ans=0,true_ans;
    for(int i=1;i<=sum;i++)
    {
        if(out[i]==0)
        {
            ans++;
            true_ans=i;
        }	
    }
    if(ans>1)	cout<<"0"<<endl;
    else cout<<num[true_ans]<<endl;//此处填num[ans]也可以过.....
    }
    return 0;
}

最后输出的地方 一开始手贱打成num[ans] 还ac了

2018/6/14 16:10
加载中...