Pagini recente » Cod sursa (job #2340708) | Cod sursa (job #105470) | Cod sursa (job #2194539) | Cod sursa (job #1488392) | Cod sursa (job #2402016)
#include <bits/stdc++.h>
using namespace std;
vector <int> v[100005];
vector <int> a[100005];
stack <int> steck;
int iden[100005], low[100005], k, i, j, ctc, l , n, m, x, y, aux;
bool onstack[100005], viz[100005];
void dfs(int x)
{
iden[x] = low[x] = ++k;
steck.push(x);
onstack[x] = true;
for(int i = 0; i < v[x].size(); i ++)
{
int aux = v[x][i];
if(viz[aux] == false)
{
viz[aux] = true;
onstack[aux] = true;
dfs(aux);
}
if(low[aux] < low[x] && onstack[aux] == true)low[x] = low[aux];
}
if(iden[x] == low[x])
{
ctc++;
while(steck.top() != x)
{
aux = steck.top();
a[ctc].push_back(aux);
onstack[aux] = false;
steck.pop();
}
aux = steck.top();
a[ctc].push_back(aux);
onstack[aux] = false;
steck.pop();
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
f >> n >> m;
for(i = 1; i <= m; i ++)
{
f >> x >> y;
v[x].push_back(y);
}
for(i = 1; i <= n; i ++)
if(viz[i] == false)k = 0, dfs(i);
g << ctc << "\n";
for(i = 1; i <= ctc; i ++)
{
for(j = 0; j < a[i].size(); j ++)
g << a[i][j] << " ";
g << "\n";
}
return 0;
}