万绿丛中一点红——Tarjian求调
查看原帖
万绿丛中一点红——Tarjian求调
1122479
xxs12345楼主2024/3/27 16:47
#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long dfn[1000001],low[1000001],jl;
long long head[1000001],nex[1000001];
long long jk[1000001],ans=1;
long long l,f[1000001];
long long d[1000001],daan;
bool br[1000001];

struct bit{
	long long x,y;
}o[1000001];

bool cmp(const bit a,const bit b){
	if(a.x==b.x) return a.y<b.y;
	return a.x<b.x;
}

void add(long long x,long long y) {
    jk[++ans]=y,nex[ans]=head[x],head[x]=ans;
    return;
}

void Tarjian(long long x,long long k)
{
	dfn[x]=low[x]=++jl;
	for(long long i=head[x];i;i=nex[i]){
		long long y=jk[i];
		if(!dfn[y]){
			Tarjian(y,i);
			low[x]=min(low[x],low[y]);
			if(low[y]>dfn[x]) br[i]=br[i^1]=1;
		}
		else if(i!=(k^1)) low[x]=min(low[x],dfn[y]);
			
	}
	return;
}

int main()
{
	freopen("P3388_6.in","r",stdin);
	freopen("P3388_6.out","w",stdout);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>m;
    for(long long i=1;i<=m;i++){
    	long long x,y;
    	cin>>x>>y;
    	f[x]++;
    	f[y]++;
    	add(x,y);//单向边 
    	add(y,x);//双向边 
	}
	for(long long i=1;i<=n;i++)
		//if(!dfn[i]) 
			Tarjian(i,0);
	for(long long i=2;i<=ans;i++){
		if(br[i]==1){
			if(f[jk[i^1]]!=1){
				l++;
				d[l]=jk[i^1];
			} 
			else 
			if(f[jk[i]]!=1){
				l++;
				d[l]=jk[i];
			} 
				
		} 
	}
	std::sort(d+1,d+l+1);
	for(long long i=1;i<=l;i++)
		if(d[i]!=d[i+1]) daan++;
	cout<<daan<<"\n";
	for(long long i=1;i<=l;i++)
		if(d[i]!=d[i+1]) cout<<d[i]<<" ";
    return 0;
} 
2024/3/27 16:47
加载中...