又又又TLE了
查看原帖
又又又TLE了
181845
luozhichen楼主2022/1/26 09:57

tarjan缩点T了!求调1

#include<bits/stdc++.h>
using namespace std;
const int MX = 1000100;
int n,m,a,b;
int fst[MX],nxt[MX],vv[MX],uu[MX],in[MX],lnum;
int stk[MX],dfn[MX],colour[MX],low[MX],vis[MX],vi[MX],d[MX],inn[MX],inn1[MX],cont,top,cnm,dnm;
namespace IO{
	const int SIZE=1<<21;
	static char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=oS+SIZE-1;
    int qr;
    char qu[55],c;
    bool f;
	#define getchar() (IO::iS==IO::iT?(IO::iT=(IO::iS=IO::ibuf)+fread(IO::ibuf,1,IO::SIZE,stdin),(IO::iS==IO::iT?EOF:*IO::iS++)):*IO::iS++)
	#define putchar(x) *IO::oS++=x,IO::oS==IO::oT?flush():0
	#define flush() fwrite(IO::obuf,1,IO::oS-IO::obuf,stdout),IO::oS=IO::obuf
	#define puts(x) IO::Puts(x)
	template<typename T>
    inline void read(T&x){
    	for(f=1,c=getchar();c<48||c>57;c=getchar())f^=c=='-';
    	for(x=0;c<=57&&c>=48;c=getchar()) x=(x<<1)+(x<<3)+(c&15); 
    	x=f?x:-x;
    }
    template<typename T>
    inline void write(T x){
        if(!x) putchar(48); if(x<0) putchar('-'),x=-x;
        while(x) qu[++qr]=x%10^48,x/=10;
        while(qr) putchar(qu[qr--]);
    }
    inline void Puts(const char*s){
    	for(int i=0;s[i];i++)
			putchar(s[i]);
		putchar('\n');
	}
	struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::write;
void add(int u,int v){
	lnum++;
	vv[lnum] = v;
	nxt[lnum] = fst[u];
	fst[u] = lnum;
	++in[v];
}
int find(){
	int ans = 0;
	for(register int i = 1;i <= a;++i){
		for(register int j = fst[d[i]]; j;j = nxt[j]){
			if(!vi[vv[j]]) ans++;
		}
	}
	//cout << ans <<endl;
	return ans;
}
void tarjan(int x)
{
	low[x] = dfn[x] = ++dnm;
	stk[++top] = x;
	vis[x] = 1;
	for(register int i = fst[x]; i;i = nxt[i])
	{
		int y = vv[i];
		if(!dfn[y]){
			tarjan(y);
			low[x] = min(low[x],low[y]);
		}else{
			if(vis[y]){
				low[x] = min(low[x],low[y]);
			}
		}
	}
	if(dfn[x] == low[x]){
		//++cnm;
		++cont;
		a = 0;
		while(x != stk[top]){
			int y = stk[top--];
			vis[y] = 0;
			d[++a] = y;
			vi[y] = 1;
			inn1[cont]++;
		}
		int y = stk[top--];
		vis[y] = 0;
		d[++a] = y;
		vi[y] = 1;
		inn1[cont]++;
		inn[cont] = find();
		a = 0;
		memset(vi,0,sizeof(vi));
	}
}
int main(){
	read(n),read(m);
	for(register int i = 1;i <= m;i++)
	{
		read(a),read(b);
		add(a,b);
	}
	for(register int i = 1;i <= n;++i)
	{
		if(!dfn[i]) tarjan(i);
	}
	int c = 0,ans;
	for(register int i = 1;i <= cont;++i){
		if(!inn[i]) c++,ans = i;
	}
	if(c == 1){
		write(inn1[ans]);
	}else{
		putchar('0');
	}
	return 0;
}

2022/1/26 09:57
加载中...