Pagini recente » Cod sursa (job #1197780) | Cod sursa (job #1135255) | Cod sursa (job #2583181) | Cod sursa (job #147698) | Cod sursa (job #2778079)
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std ;
ifstream cin("ctc.in") ;
ofstream cout("ctc.out") ;
int n ;
int verif[100009] ;
int paths[109][109] ;
vector<int> m[100009] ;
void fil(int nod, int acata)
{
verif[nod] = 1 ;
paths[nod][acata] = acata ;
for(int f = 0 ; f < m[nod].size() ; f ++)
if(!verif[m[nod][f]])fil(m[nod][f], acata) ;
}
vector<int> curenta ;
int deja_adaugat[109] ;
bool adauga_noduri()
{
/// incearca fiecare nod care nu este deja adaugat
for(int f = 1 ; f <= n ; f ++)
if(!deja_adaugat[f])
{
/// verificam daca putem duce path de la el la orice altii si de la orice altii la el
int ok = 1 ;
for(int e = 0 ; e < curenta.size() ; e ++)
if(!paths[curenta[e]][f] || !paths[f][curenta[e]])
ok = 0 ;
if(ok)curenta.push_back(f), deja_adaugat[f] = 1 ;
}
}
int main()
{
int q ;
cin >> n >> q ;
while(q --)
{
int a, b ;
cin >> a >> b ;
m[a].push_back(b) ;
}
for(int f = 1 ; f <= n ; f ++)
{
fil(f, f) ;
for(int e = 1 ; e <= n ; e ++)
verif[e] = 0 ;
}
int rez = 0 ;
vector<vector<int> > fin ;
for(int f = 1 ; f <= n ; f ++)
{
curenta.push_back(f) ;
deja_adaugat[f] = 1 ;
adauga_noduri() ;
if(curenta.size() >= 2)rez ++, fin.push_back(curenta) ;
curenta.clear() ;
}
cout << rez << endl ;
for(int f = 0 ; f < fin.size() ; f ++)
{
for(int e = 0 ; e < fin[f].size() ; e ++)
cout << fin[f][e] << " " ;
cout << '\n' ;
}
return 0 ;
}