Pagini recente » Cod sursa (job #744679) | Cod sursa (job #152533) | Cod sursa (job #272663) | Cod sursa (job #1495708) | Cod sursa (job #2604044)
#include <iostream>
#include <vector>
#include <stdio.h>
#define pb push_back
#define NMAX 100001
using namespace std;
vector<unsigned> v[NMAX], comp;
vector<bool> viz;
unsigned N, M, cont;
bool conect;
void dfs2(unsigned src, unsigned dest)
{
viz[src] = true;
for(unsigned i = 0; i < v[src].size() && !conect; ++i)
if(v[src][i] == dest)
{
conect = true;
return;
}
else if(!viz[v[src][i]])
dfs2(v[src][i], dest);
}
void reset()
{
for(unsigned i = 1; i <= N; viz[i++] = false);
}
int main()
{
freopen("ctc.in", "r", stdin);
cin >> N >> M;
for(unsigned i = 1; i <= M; ++i)
{
unsigned x, y;
cin >> x >> y;
v[x].pb(y);
}
fclose(stdin);
comp.resize(N + 1);
viz.resize(N + 1);
reset();
vector<unsigned> c[NMAX];
for(unsigned i = 1; i <= N; ++i)
{
bool gasit = false;
for(unsigned j = 1; j < i; ++j)
{
conect = false;
dfs2(i, j);
reset();
if(!conect)
continue;
conect = false;
dfs2(j, i);
reset();
if(conect)
{
c[comp[j]].pb(i);
comp[i] = comp[j];
gasit = true;
break;
}
}
if(!gasit)
{
comp[i] = ++cont;
c[cont].pb(i);
}
}
freopen("ctc.out", "w", stdout);
cout << cont;
for(unsigned i = 1; i <= cont; ++i)
{
cout << endl;
for(auto k : c[i])
cout << k << ' ';
}
fclose(stdout);
return 0;
}