Pagini recente » Cod sursa (job #364112) | Cod sursa (job #2599992) | Cod sursa (job #3285912) | Cod sursa (job #1759071) | Cod sursa (job #1909645)
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
#define NMAX 100001
int n, m, lg, vf;
vector <int> G[NMAX], Gt[NMAX], CTC[NMAX];
int Use[NMAX], Stiva[NMAX];
void dfs_comp(int node) {
int i, vecin;
Use[node] = 1;
for(i = 0; i < G[node].size(); i++) {
vecin = G[node][i];
if(!Use[vecin])
dfs_comp(vecin);
}
Stiva[++vf] = node;
}
void dfs_create(int node) {
int i, vecin;
Use[node] = 1; CTC[lg].push_back(node);
for(i = 0; i < Gt[node].size(); i++) {
vecin = Gt[node][i];
if(!Use[vecin])
dfs_create(vecin);
}
}
int main()
{
int i, j, x, y;
///citire
f>>n>>m;
for(i = 1; i <= m; i++) {
f>>x>>y;
G[x].push_back(y);
Gt[y].push_back(x);
}
for(i = 1; i <= n; i++)
if(!Use[i])
dfs_comp(i);
memset(Use, 0, NMAX);
while(vf) {
i = Stiva[vf--];
if(!Use[i]) {
lg++;
dfs_create(i);
}
}
g<<lg<<'\n';
for(i = 1; i <= lg; i++) {
for(j = 0; j < CTC[i].size(); j++)
g<<CTC[i][j]<<' ';
g<<'\n';
}
return 0;
}