90TLE,蒟蒻求助
查看原帖
90TLE,蒟蒻求助
290055
jr_inf楼主2021/8/11 14:41

最后一个点开o2也过不了

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;
int n,a,b,dfn[200010],low[200010],iscp[200010],ans,ind;
bool flag,f[200010];
vector<int> g[200010];
int min(int a,int b)
{
	if(a < b) return a;
	return b;
}
void dfs(int u,int gd)
{
	if(flag) return;
	if(u == b)
	{
		flag = 1;
		return;
	}
	for(int i = 0;i < g[u].size();i++)
	{
		int v = g[u][i];
		if(v != gd && !f[v])
		{
			f[v] = 1;
			dfs(v,gd);
		}
	}
	return;
}
void fcp(int u,int fa)
{
    int child = 0;
    dfn[u] = low[u] = ++ind;
    for(int i = 0;i < g[u].size();i++)
    {
        int v = g[u][i];
        if(!dfn[v])
        {
            child++;
            fcp(v,u);
            low[u] = min(low[u],low[v]);
            if(low[v] >= dfn[u]) iscp[u] = 1;
        }
		else if(v != fa) low[u] = min(low[u],dfn[v]);
    }
    if(fa < 0 && child == 1) iscp[u] = 0;
}
int main()
{
	scanf("%d",&n);
	int u,v;
	while(scanf("%d%d",&u,&v))
	{
		if(!u && !v) break;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	scanf("%d%d",&a,&b);
    for(int i = 1;i <= n;i++)
    {
        if(dfn[i] == 0)
        {
            ind = 0;
            fcp(i,-1);
        }
    }
    for(int i = 1;i <= n;i++)
	{
		if(iscp[i])
		{
			memset(f,0,sizeof(f));
			flag = 0;
			dfs(a,i);
			if(!flag)
			{
				printf("%d",i);
				return 0;
			}
		}
	}
	printf("No solution");
}
2021/8/11 14:41
加载中...