Pagini recente » Cod sursa (job #2398382) | Cod sursa (job #2193415) | Cod sursa (job #743297) | Cod sursa (job #3159325) | Cod sursa (job #968109)
Cod sursa(job #968109)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
#define LE 100666
#define pb push_back
#define x first
#define y second
vector<int> H[LE],graf_2[LE],result[LE];
int K,level[LE],max_up[LE];
bool viz[LE];
void dfs(int nod) {
int N=H[nod].size(),i;
max_up[nod]=level[nod];
for(i=0; i<N; ++i) {
if (level[H[nod][i]]==0) {
level[H[nod][i]]=level[nod]+1;
dfs(H[nod][i]);
if (max_up[H[nod][i]]<=level[nod]) {
graf_2[nod].pb(H[nod][i]);
graf_2[H[nod][i]].pb(nod);
}
}
max_up[nod]=min(max_up[nod],level[H[nod][i]]);
max_up[nod]=min(max_up[nod],max_up[H[nod][i]]);
}
}
void dfs_2(int nod) {
viz[nod]=true;
int N=graf_2[nod].size(),i;
result[K].pb(nod);
for(i=0; i<N; ++i)
if (viz[graf_2[nod][i]]==false)
dfs_2(graf_2[nod][i]);
}
int main() {
int n,m,i,xx,yy;
f>>n>>m;
for(i=1; i<=m; ++i) {
f>>xx>>yy;
H[xx].pb(yy);
}
for(i=1; i<=n; ++i)
if (level[i]==0) {
level[i]=1;
dfs(i);
}
for(i=1; i<=n; ++i)
if (viz[i]==false) {
++K;
dfs_2(i);
}
g<<K<<'\n';
for(i=1; i<=K; ++i,g<<'\n') {
int N=result[i].size(),j;
for(j=0; j<N; ++j)
g<<result[i][j]<<" ";
}
f.close();
g.close();
return 0;
}