QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#478728#906. 强连通分量PYD1#WA 0ms21712kbC++142.1kb2024-07-15 10:39:212024-07-15 10:39:21

Judging History

你现在查看的是最新测评结果

  • [2024-07-15 10:39:21]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:21712kb
  • [2024-07-15 10:39:21]
  • 提交

answer

#include <set>
#include <map>
#include <list>
#include <queue>
#include <cmath>
#include <time.h>
#include <random>
#include <bitset>
#include <vector>
#include <cstdio>
#include <stdio.h>
#include <iomanip>
#include <assert.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define mk make_pair
#define fi first
#define se second

char buf[1 << 20],*p1,*p2;
inline char gc(){
	if (p1 == p2){
		p1 = buf;
		p2 = buf + fread(buf,1,1 << 20,stdin);
	}
	return p1 == p2 ? EOF : *p1++;
	// return getchar();
}

inline int read(){
	int t = 0,f = 1;
	register char c = gc();
	while (c < 48 || c > 57) f = (c == '-') ? (-1) : (f),c = gc();
	while (c >= 48 && c <= 57) t = (t << 1) + (t << 3) + (c ^ 48),c = gc();
	return f * t;
}

const int N = 5e5 + 3,M = 5e5 + 3;
int n,m,etot = 1,dfncnt,stop,scccnt,head[N],dfn[N],low[N],scc[N],stk[N];
bool instk[N];

struct Edge{
	int u,v,nxt;
}e[M];

inline void adde(int u,int v) {e[++etot] = (Edge){u,v,head[u]},head[u] = etot;}

vector <int> bel[N];

void Tarjan(int u){
	dfn[u] = low[u] = ++dfncnt;instk[stk[++stop] = u] = 1;
	for (int i = head[u];i;i = e[i].nxt){
		int v = e[i].v;
		if (!dfn[v]) Tarjan(v),low[u] = min(low[u],low[v]);
		else if (instk[v]) low[u] = min(low[u],dfn[v]);
	}
	if (low[u] >= dfn[u]){
		++scccnt;int v;
		do{
			v = stk[stop--],scc[v] = scccnt,bel[scccnt].emplace_back(v);
			instk[v] = 0;
		}while (v != u);
	}
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
#endif
	n = read(),m = read();
	for (int i = 1;i <= m;i++){
		int u = read(),v = read();
		adde(u,v);
	}
	for (int i = 0;i < n;i++) if (!dfn[i]) Tarjan(i);
	printf("%d\n",scccnt);
	for (int i = 1;i <= scccnt;i++){
		printf("%d ",(int)bel[i].size());
		sort(bel[i].begin(),bel[i].end());
		for (int p : bel[i]) printf("%d ",p);puts("");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 21712kb

input:

6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2

output:

4
2 0 3 
1 2 
2 1 4 
1 5 

result:

wrong answer 5 is later than 2, but there is an edge (5, 2)