Pagini recente » Cod sursa (job #2880458) | Cod sursa (job #1047603) | Cod sursa (job #2533060) | Cod sursa (job #3202801) | Cod sursa (job #1335301)
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define MAX 100003
vector <int> gr[MAX], comp[MAX];
stack <int> s, afis;
bitset <MAX> bs;
int n, m, id[MAX], low[MAX], nc, urm;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
void tarjan(int nod){
id[nod] = low[nod] = ++urm;
s.push(nod);
bs[nod] = 1;
for(unsigned i=0; i<gr[nod].size(); i++)
if(id[gr[nod][i]]==0){
tarjan(gr[nod][i]);
low[nod] = min(low[nod], low[gr[nod][i]]);
}
else
if(bs[nod]==1)
low[nod] = min(low[nod], low[gr[nod][i]]);
if(id[nod] == low[nod]){
nc++;
int v;
do{
v = s.top();
s.pop(); bs[v] = 0;
afis.push(v);
}while(v!=nod);
}
}
int main()
{
int i, u, v;
fin>>n>>m;
for(i=1; i<=m; i++){
fin>>u>>v;
gr[u].push_back(v);
}
for(i=1; i<=n; i++)
if(id[i]==0)
tarjan(i);
fout<<nc;
while(!afis.empty()){
int v = afis.top();
afis.pop();
if(id[v] == low[v]) fout<<'\n';
fout<<v<<' ';
}
return 0;
}