Pagini recente » Cod sursa (job #3275310) | Clasamentul arhivei de probleme | Cod sursa (job #2199017) | Cod sursa (job #253215) | Cod sursa (job #2120962)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
FILE *f = fopen("ctc.in","r");
FILE *g = fopen("ctc.out","w");
vector<int> G[100005];
vector<vector<int> > ctc;
bool inst[100005];
int st[100005];
int len;
int id[100005];
int low[100005];
int lastid;
int N,M;
void dfs(int nod){
st[++len] = nod;
inst[nod] = 1;
id[nod] = low[nod] = ++lastid;
for(auto it:G[nod]){
if(!id[it]){
dfs(it);
}
if(inst[it]){
low[nod] = min(low[nod],low[it]);
}
}
if(low[nod] == id[nod]){
vector<int> tmp;
while(st[len] != nod){
tmp.push_back(st[len]);
inst[st[len]] = 0;
len--;
}
tmp.push_back(st[len]);
inst[st[len]] = 0;
len--;
ctc.push_back(tmp);
}
}
int main() {
fscanf(f,"%d %d",&N,&M);
for(int i = 1;i <= M;i++){
int x,y;
fscanf(f,"%d %d",&x,&y);
G[x].push_back(y);
}
for(int i = 1;i <= N;i++){
if(!id[i]){
dfs(i);
}
}
fprintf(g,"%d\n",(int)ctc.size());
for(auto it:ctc){
for(auto it2:it){
fprintf(g,"%d ",it2);
}
fprintf(g,"\n");
}
fclose(f);
fclose(g);
return 0;
}