Pagini recente » Cod sursa (job #1914106) | Cod sursa (job #1014921) | Cod sursa (job #96723) | Cod sursa (job #2378991) | Cod sursa (job #2528592)
#include <fstream>
#include <stack>
#include <bitset>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, i, j, k, x, y, componente, niv[100010], low[100010];
stack <int> s;
bitset <100010> IS;
vector<int> a[100010], sol[100010];
void dfs(int nod){
k++;
niv[nod]=k;
low[nod]=k;
s.push(nod);
IS[nod]=1;
for(int i=0; i<a[nod].size(); i++) {
int vecin=a[nod][i];
if(niv[vecin]==0) {
dfs(vecin);
low[nod]=min(low[nod], low[vecin]);
}else{
if(IS[vecin]!=0){
low[nod]=min(low[nod], low[vecin]);
}
}
}
if(niv[nod]==low[nod]){
componente++;
int aux;
do{
aux=s.top();
s.pop();
IS[aux] = 0;
sol[componente].push_back(aux);
}while(aux!=nod);
}
}
int main() {
fin>>n>>m;
for (i=1; i<=m; i++) {
fin>>x>>y;
a[x].push_back(y);
}
for (i=1;i<=n;i++){
if (niv[i]==0){
dfs(i);
}
}
fout<<componente<<"\n";
for (i=1; i<=componente; i++){
for (j=0; j<sol[i].size(); j++){
fout<<sol[i][j]<<" ";
}
fout<<"\n";
}
}