Submission #76969058

---

Source Code Expand

#pragma GCC optimize("inline,Ofast",2)
#pragma GCC optimize("inline,Ofast",3)
#include<cstdio>
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<map>
#include<iomanip>
#include<vector>
#include<set>
#include<deque>
#include<ctime>
#include<cstdlib>
#include<bitset>
#include<utility>
#include<climits>
using namespace std;
#define fir first
#define sec second
#define db double
#define ld long db
#define ll long long
#define ull unsigned ll
#define ui unsigned
#define i128 __int128
#define u128 unsigned i128
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define wln(x) output(x),putchar(10)
#define wls(x) output(x),putchar(32)
char gc()
{
	char c=getchar();
	while(c==10 or c==13)c=getchar();
	return c;
}
template<class T>void read(T &x)
{
	x=0;bool f=0;
	char c=getchar();
	for(;!isdigit(c);c=getchar())f|=c==45;
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x=f?-x:x;
}
template<class T>void output(T x)
{
	if(!x)return putchar(48),void();
	if(x<0)putchar(45),x=-x;
	int num[50]={},cnt=0;
	while(x)num[++cnt]=x%10,x/=10;
	for(int i=cnt;i;--i)putchar(48|num[i]);
}
const int N=200007;
int n,m,q;
int head[N],tot,dfs_clock;
int col,co[N],dfn[N],siz[N],low[N];
stack<int>s;
struct sch{int to,next;}a[N<<1];

void add(int u,int v){a[++tot]=(sch){v,head[u]};head[u]=tot;}
void tarjan(int u)
{
	s.push(u);
	low[u]=dfn[u]=++dfs_clock;
	for(int to,i=head[u];i;i=a[i].next)
		if(!dfn[to=a[i].to])
		{
			tarjan(to);
			low[u]=min(low[u],low[to]);
		}
		else if(!co[to])low[u]=min(low[u],dfn[to]);
	if(dfn[u]==low[u])
	{
		co[u]=++col;
		siz[col]=1;
		while(s.top()!=u)
		{
			co[s.top()]=col;
			++siz[col];
			s.pop();
		}
		s.pop();
	}
}
signed main()
{
	//freopen("G.in","r",stdin);
	//freopen("G.out","w",stdout);
	read(n),read(m);
	for(int i=1,u,v;i<=m;++i)
	{
		read(u),read(v);
		add(u,v);add(v,u);
	}
	for(int i=1;i<=n;++i)
		if(!dfn[i])
			tarjan(i);
	read(q);
	while(q--)
	{
		int id;
		read(id);
		wln(siz[co[id]]);
	}
	return 0;
}

Submission Info

Judge Result