Pagini recente » Cod sursa (job #2503196) | Cod sursa (job #59450) | Cod sursa (job #2144410) | Cod sursa (job #134193) | Cod sursa (job #3164729)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int nmax = 100003;
int n, m, index;
int viz[nmax];
vector <int> g[nmax];
vector <int> gTranspus[nmax];
vector <int> ctc[nmax];
void dfs(int nod);
void dfsTranspus(int nod);
void read(void);
void reset(void);
int main(){
int i, j;
read();
for(i = 1; i <= n; i++){
if(viz[i] != 2){
dfs(i);
dfsTranspus(i);
reset();
index++;
}
}
fout<<index<<"\n";
for(i = 0; i < index; i++){
for(j = 0; j < ctc[i].size(); j++)
fout<<ctc[i][j]<<" ";
fout<<"\n";
}
}
void read(void){
int i, j;
fin>>n>>m;
while(m--){
fin>>i>>j;
g[i].push_back(j);
gTranspus[j].push_back(i);
}
}
void dfs(int nod){
int i, vecin;
viz[nod]++;
for(i = 0; i < g[nod].size(); i++){
vecin = g[nod][i];
if(!viz[vecin])
dfs(vecin);
}
}
void dfsTranspus(int nod){
int i, vecin;
viz[nod]++;
ctc[index].push_back(nod);
for(i = 0; i < gTranspus[nod].size(); i++){
vecin = gTranspus[nod][i];
if(viz[vecin] == 1)
dfsTranspus(vecin);
}
}
void reset(void){
int i;
for(i = 1; i <= n; i++)
if(viz[i] != 2)
viz[i] = 0;
}