Pagini recente » Cod sursa (job #2649367) | Cod sursa (job #2272552) | Cod sursa (job #1767114) | Cod sursa (job #1075063) | Cod sursa (job #1607525)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m, i, j, nr, niv[100010], low[100010], viz[100010], t, aux, x, y;
vector<int> l[100010], c[100010];
stack<int> st;
void dfs(int x){
t++;
niv[x]=low[x]=t;
st.push(x);
viz[x]=1;
for(int i=0; i<l[x].size(); i++)
{
if(viz[ l[x][i] ]==0){
dfs(l[x][i]);
low[x]=min(low[x], low[ l[x][i] ]);
}
else
low[x]=min(low[x], niv[ l[x][i] ]);
}
if(niv[x]==low[x])
{
nr++;
do
{
aux=st.top();
c[nr].push_back(aux);
st.pop();
}while(x!=aux);
}
}
int main(){
f>>n>>m;
for(i=1; i<=m; i++)
{
f>>x>>y;
l[x].push_back(y);
}
for(i=1; i<=n; i++)
if(viz[i]==0)
dfs(i);
g<<nr<<"\n";
for(i=1; i<=nr; i++)
{
for(j=0; j<c[i].size(); j++)
g<<c[i][j]<<' ';
g<<"\n";
}
return 0;
}