这是我的代码c++14
#include<bits/stdc++.h>
using namespace std;
#define int __int128
const int N=100005;
int rd()
{
int x=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
return x;
}
int head[N][2],tot[2];
struct edge
{
int v,to;
}e[N>>1][2];
void add(int u,int v)
{
e[++tot[0]][0].v=v;
e[tot[0]][0].to=head[u][0];
head[u][0]=tot[0];
e[++tot[1]][1].v=u;
e[tot[1]][1].to=head[v][1];
head[v][1]=tot[1];
}
int n,m,p[N],q[N],d[N],in[N];
bool flag[N];
vector<int>out;
queue<int>que;
stack<int>s;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
void yf(int &a,int &b)
{
int c=gcd(a,b);
a/=c;b/=c;
}
void print(int x)
{
if(x>9)print(x/10);
putchar(x%10+'0');
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.ans","w",stdout);
n=rd();m=rd();//print(n);putchar(' ');print(m);putchar('\n');
for(int i=1;i<=n;i++)
{
d[i]=rd();
in[i]=d[i];//print(d[i]);putchar(' ');
for(int j=0,v;j<d[i];j++)
{
v=rd();//print(v);putchar(' ');
add(v,i);
flag[v]=1;
}//putchar('\n');
if(d[i]==0)out.push_back(i);
q[i]=1;
}
for(int i=1;i<=n;i++)if(!flag[i])p[i]=1;
for(int i=0;i<out.size();i++)que.push(out[i]);
int res;
while(!que.empty())
{
res=que.front();
que.pop();
for(int i=head[res][0];i;i=e[i][0].to)
{
int v=e[i][0].v;
if(!--in[v])que.push(v);
}
s.push(res);
}
/*while(!s.empty())
{
printf("%d ",s.top());
s.pop();
}puts("");*/
while(s.size()!=out.size())
{
res=s.top();
s.pop();
int a=p[res],b=q[res]*d[res];
yf(a,b);
for(int i=head[res][1];i;i=e[i][1].to)
{
int v=e[i][1].v;
p[v]=b*p[v]+a*q[v];
q[v]*=b;
yf(p[v],q[v]);
}
}
//printf("%d\n",out.size());
for(int i=0;i<out.size();i++)
{
// print(out[i]);
// putchar(':');
print(p[out[i]]);
putchar(' ');
print(q[out[i]]);
putchar('\n');
}
return 0;
}
/*
*/
60分,莫名输出一堆“0 1”
下载数据后发现这输入n=1e5后就输入1万多行是什么鬼?
(49~59行解除注释,97~105行注释即可看输入)
人傻常数大,代码很菜,跪求别喷