WA 44pts 求助
查看原帖
WA 44pts 求助
767561
Ascnbeta楼主2023/12/17 22:28

大思路基本照着一号题解打的

不知道为啥死活过不去

#include <bits/stdc++.h>
#define N 10100
using namespace std;
int all[N],deg[N]; 
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline void MIN(int &a, int b) {
	if (b < a) a = b;
}
inline void MAX(int &a, int b) {
	if (b > a) a = b;
}
int n, m;
struct edge {
	int nxt, to;
	edge(){}
	edge(int u, int v) { nxt = u, to = v; }
}e[N << 1];
int head[N], ecnt;
inline void addedge(int u, int v) {
	if (u == v) return;
	e[++ecnt] = edge(head[u], v);
	head[u] = ecnt;
}
int dfn[N], low[N], dcnt;
int stk[N], stop;
bool instk[N];
int col[N], ctot;
void tarjan(int cur) {
	dfn[cur] = low[cur] = ++dcnt; 
	stk[++stop] = cur;
	instk[cur] = true;
	for (int i = head[cur]; i; i = e[i].nxt) {
		int to = e[i].to;
		if (!dfn[to]) tarjan(to), MIN(low[cur], low[to]);
		else if (instk[to]) MIN(low[cur], dfn[to]);
	}
	int tmp;
	if (low[cur] == dfn[cur]) {
		++ctot;
		
		do {
			tmp = stk[stop--];
			instk[tmp] = false;
			col[tmp] = ctot;
			all[ctot]++;
		} while (tmp != cur);
	}
}

vector<int> ve[N];
int outd[N];
inline void aded(int u, int v) {
	ve[v].push_back(u);
	++outd[u];
}
int que[N], front, rear;
int f[N];
int main() {
	n = read(), m = read();
	for (int i = 1; i <= m; ++i) {
		int u = read(), v = read();
		addedge(u, v);
	}
	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 = e[j].nxt) {
			int to = e[j].to;
			if (col[i] != col[to]) deg[col[j]]++;
		}
	}
    int temp = 0;
    for (int i = 1; i <= ctot; i++) {
        if (!deg[i]){
            if (temp) {
				cout << 0 << endl;
				return 0;
			}
            temp = i;
        }
	}
    printf("%d\n",all[temp]);
	return 0;
}
2023/12/17 22:28
加载中...