Pagini recente » Cod sursa (job #861717) | Cod sursa (job #2719633) | Cod sursa (job #2395996) | Cod sursa (job #3142647) | Cod sursa (job #1336817)
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
#include <algorithm>
using namespace std;
#define MAX 100005
void dfs(int nod);
vector<int> graf[MAX];
stack<int> st, afis;
bitset<MAX> bit;
int vid[MAX], vlow[MAX], nextt, nc, n, m;
int main()
{
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int i, a, b;
fin>>n>>m;
for(i=1; i<=m; i++)
{
fin>>a>>b;
graf[a].push_back(b);
}
for(i=1; i<=n; i++)
if(!vid[i])
dfs(i);
fout<<nc;
while(!afis.empty())
{
if(vid[afis.top()] == vlow[afis.top()])
fout<<'\n';
fout<<afis.top()<<' ';
afis.pop();
}
return 0;
}
void dfs(int nod)
{
int i, fiu;
nextt++;
vid[nod] = vlow[nod] = nextt;
st.push(nod);
bit[nod] = 1;
for(i=0; i<graf[nod].size(); i++)
{
fiu = graf[nod][i];
if(!vid[fiu])
{
dfs(fiu);
vlow[nod] = min(vlow[nod], vlow[fiu]);
}
else
if(bit[fiu])
vlow[nod] = min(vlow[nod], vlow[fiu]);
}
if(vid[nod] == vlow[nod])
{
nc++;
do
{
afis.push(st.top());
bit[st.top()] = 0;
st.pop();
}while(afis.top() != nod);
}
}