This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef vector <lli> vi;
set<int> al[500001];
int n,m,t,c=0;
int par[500001],r[500001]={};
vector<ii> ed;
int find(int f)
{
if(par[par[f]]!=par[f]) par[f]=find(par[f]);
return(par[f]);
}
void mer(int f,int s)
{
int pf=find(f),ps=find(s);
if(pf!=ps)
{
if(r[pf]>=r[ps])
{
par[ps]=pf;
r[pf]++;
}
else
{
par[pf]=ps;
r[ps]++;
}
t--;
}
}
int main()
{
cin>>n>>m;
t=n;
for(int i=1;i<=n;++i)
{
par[i]=i;
r[i]=1;
}
for(int i=0;i<m;++i)
{
char c;
int f,s;
cin>>f>>s>>c;
if(c=='A')
ed.pb(mp(f,s));
else
mer(f,s);
}
for(int i=0;i<ed.size();++i)
{
int pf=find(ed[i].F),ps=find(ed[i].S);
al[pf].insert(ps);
al[ps].insert(pf);
}
for(int i=1;i<=n;++i)
if(al[find(i)].size()==t-1)
c++;
cout<<c<<endl;
return(0);
}
Compilation message (stderr)
menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ed.size();++i)
~^~~~~~~~~~
menesinis_bilietas.cpp:70:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(al[find(i)].size()==t-1)
~~~~~~~~~~~~~~~~~~^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |