QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#478728 | #906. 强连通分量 | PYD1# | WA | 0ms | 21712kb | C++14 | 2.1kb | 2024-07-15 10:39:21 | 2024-07-15 10:39:21 |
Judging History
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;
}
詳細信息
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)