Pagini recente » Cod sursa (job #1222271) | Cod sursa (job #1797467) | Cod sursa (job #2725988) | Cod sursa (job #1915357) | Cod sursa (job #1495156)
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>
#include<stack>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N,M,nrcomp;
int a[5005][5005];
vector<int> v[5005];
vector<int> componente[5005];
bitset<5005> verif;
void dfs(int);
int main()
{
f>>N>>M;
FOR (i,1,M) {
int x,y;
f>>x>>y;
a[x][y]=1;
}
FOR (i,1,N) {
a[i][i]=1;
}
FOR (k,1,N) {
FOR (i,1,N) {
FOR (j,1,N) {
a[i][j]=a[i][j] | (a[i][k] & a[k][j]);
}
}
}
FOR (i,1,N) {
FOR (j,1,N) {
if (a[i][j] && a[j][i]) {
v[i].pb(j);
v[j].pb(i);
}
}
}
FOR (i,1,N) {
if (!verif.test(i)) {
++nrcomp;
dfs(i);
}
}
g<<nrcomp<<'\n';
FOR (i,1,nrcomp) {
vector<int>::iterator it;
for (it=componente[i].begin();it<componente[i].end();++it) {
g<<(*it)<<' ';
}
g<<'\n';
}
f.close();g.close();
return 0;
}
void dfs(int nod) {
verif.set(nod,1);
componente[nrcomp].pb(nod);
for (unsigned int k=0;k<v[nod].size();++k) {
if (!verif.test(v[nod][k])) {
dfs(v[nod][k]);
}
}
}