Pagini recente » Cod sursa (job #2940753) | Cod sursa (job #1609723) | Cod sursa (job #2955863) | Cod sursa (job #2940758) | Cod sursa (job #3322645)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 100000;
int N, M, nrc;
vector<int> G[NMAX + 1], CTC[NMAX + 1];
int D[NMAX + 1], Dmin[NMAX + 1], Timp = 0;
stack<int> S;
bool inSt[NMAX + 1]; ///inSt[i] = 1 <==> i este in stiva
ifstream f("ctc.in");
ofstream g("ctc.out");
void citire() {
int x, y;
f >> N >> M;
for(int i = 1; i <= M; i++) {
f >> x >> y;
G[x].push_back(y);
}
}
void DFS(int x) {
D[x]=++Timp;
Dmin[x]=D[x];
S.push(x);
inSt[x]=1;
for(const auto&y:G[x]) {
if(D[y]==0) { ///muhcie de arbore
DFS(y);
Dmin[x]=min(Dmin[x],Dmin[y]);
} else {
if(inSt[y]==1) {
Dmin[x]=min(Dmin[x],D[y]);
}
}
}
if(Dmin[x]==D[x]) {
int u;
nrc++;
do {
u=S.top();
CTC[nrc].push_back(u);
S.pop();
inSt[u]=0;
} while(x!=u);
}
}
void afisare() {
g<<nrc<<'\n';
for(int i=1; i<=nrc; i++) {
for(const auto&x:CTC[i]) {
g<<x<<' ';
}
g<<'\n';
}
}
int main() {
citire();
for(int i=1; i<=N; i++) {
if(D[i]==0) {
DFS(i);
}
}
afisare();
f.close();
g.close();
return 0;
}