Pagini recente » Cod sursa (job #438897) | Cod sursa (job #906687) | Statistici Stefan Bosie (Stefan07) | Cod sursa (job #1726168) | Cod sursa (job #1662340)
#include <fstream>
#include <cstring>
#include <vector>
#define NMAX 200005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int lst[NMAX] , urm[NMAX] , vf[NMAX] , lstt[NMAX] , vft[NMAX] , urmt[NMAX] , viz[NMAX] , ctc[NMAX];
int n , m , nr , nrc , x , y , nrt;
vector <vector <int> > c;
void dfs(int x);
void dfst(int x);
void adauga(int pos , int x);
int main() {
f >> n >> m;
for(int i = 1 ; i <= m ; ++i) {
f >> x >> y;
++nr;
vf[nr] = y;
urm[nr] = lst[x];
lst[x] = nr;
++nrt;
vft[nrt] = y;
urmt[nrt] = lstt[x];
lstt[x] = nrt;
}
for(int i = 1 ; i <= n ; ++i) {
if(viz[i] == 0) {
dfs(i);
}
}
memset(viz , 0 , sizeof(viz));
c.resize(nrc + 5);
nr = 0;
for(int i = 1 ; i <= n ; ++i) {
if(viz[ctc[i]] == 0) {
++nr;
dfst(ctc[i]);
}
}
g << nr << '\n';
for(int i = 1 ; i <= nr ; ++i) {
//g << c[i].size() << " ";
for(vector <int> :: iterator it = c[i].begin() ; it != c[i].end() ; ++it) {
g << *it << " ";
}
g << '\n';
}
return 0;
}
void dfs(int x) {
viz[x] = 1;
int p , y;
p = lst[x];
while(p != 0) {
y = vf[p];
if(!viz[y]) {
dfs(y);
}
p = urm[p];
}
ctc[++nrc] = x;
}
void dfst(int x) {
viz[x] = 1;
int p , y;
p = lstt[x];
adauga(nr , x);
while(p != 0) {
y = vft[p];
if(!viz[y]) {
dfst(y);
}
p = urmt[p];
}
}
void adauga(int pos , int x) {
c[pos].push_back(x);
}